///dijkstra
priority_queue < pair < int,int > > q;
vector < pair < int,int > > v[N];
int dis[N];
void dijkstra(int s, int n){
    int i;
    for(i = 1; i<=n; i++) dis[i] = MAX;
    dis[s] = 0;
    q.push(mp(0,s));
    pair < int,int > p;
    while(!q.empty()){
        p = q.top();
        q.pop();
        s = p.second;
        if(dis[s]<-p.first) continue;
        for(i = 0; i<v[s].size(); i++){
            if(dis[v[s][i].first]>dis[s]+v[s][i].second){
                dis[v[s][i].first] = dis[s]+v[s][i].second;
                q.push(mp(-dis[v[s][i].first],v[s][i].first));
            }
        }
    }
}