const int N=1e5+5,inf=0x3f3f3f3f;
int n,dis[N],vis[N];
vector<pair<int,int>> G[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
void dijkstra () {
    for (int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=0;
    pq.push ({0,1});
    while (pq.size()) {
        pair<int,int> top=pq.top (); pq.pop ();
        if (vis[top.second]) continue;
        vis[top.second]=1;
        for (auto e: G[top.second]) {
            if (dis[e.first]>top.first+e.second) {
                dis[e.first]=top.first+e.second;
                pq.push ({dis[e.first],e.first});
            }
        }
    }
}