struct node

{

	long long x,d;

	node();

	node(long long xx,long long dd){

		x = xx;

		d = dd;

	}

};

vector<node> edge[maxn];

void dijkstra(long long x)

{

	long long i,j;

	for(i=0;i<n;i++) vis[i] = 0,dis[i] = INF;

	dis[x] = 0;

	for(i=0;i<n;i++){

		long long minn = INF;

		long long u = 0;

		for(j=0;j<n;j++){

			if(!vis[j] && minn > dis[j]){

				minn = dis[j];

				u = j;

//                cout<<"A "<<minn<<" "<<u<<endl;

			}

		}

        vis[u] = 1;

		for(j=0;j<edge[u].size();j++){

            long long v = edge[u][j].x;

			if(!vis[v] && (minn + edge[u][j].d) < dis[v])

				dis[v] = minn + edge[u][j].d;

		}

	}

}

const int MAXN = ;

const ll INF = ((ll)<<);

struct node{

    int x;

    ll d;

    node(){}

    node(int a,ll b){x = a;d = b;}

    bool operator < (const node & a) const

    {

        if(d == a.d) return x < a.x;

        else return d > a.d;

    }

};

vector<node> edge[MAXN];    //记得清边

ll dis[MAXN];

int N;  //N从1到N

void Dijkstra(int s)

{

    for(int i = ; i <= N; i++) dis[i] = INF;

    dis[s] = ;

    priority_queue<node> q;

    q.push(node(s,dis[s]));

    while(!q.empty()){

        node x = q.top();

        q.pop();

        for(int i = ;i < edge[x.x].size(); i++){

            node y = edge[x.x][i];

            if(dis[y.x] > x.d + y.d){

                dis[y.x] = x.d + y.d;

                q.push(node(y.x,dis[y.x]));

            }

        }

    }

}