#include<bits/stdc++.h>

#define inf 1<<30

using namespace std;

struct Edge{

    int nex,to,w;

}edge[1000000];

int cnt;

int n;

inline void add(int u,int v,int w){

    edge[cnt].to=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt++;

}

int dis[10000000];

void spfa(int s){

    queue<int>q;

    bool vis[100000];

    memset(vis,0,sizeof vis);

    vis[s]=1;

    dis[s]=0;

    q.push(s);

    while(!q.empty()){

        int f=q.front();

        q.pop();

        vis[f]=0;

        for(int i=head[f];~i;i=edge[i].nex){

            int v=edge[i].to;

            if(dis[v]>dis[f]+edge[i].w){

                dis[v]=dis[f]+edge[i].w;

                if(!vis[v]){

                    vis[v]=1;

                    q.push(v);

                }

            }

        }

    }

}

int main()

{

    return 0;

}