#define ip pair<int, int>
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
         vector<vector<ip>> neighbors(n + 1);
        for (auto &t : times)
            neighbors[t[0]].emplace_back(t[1], t[2]);

            vector<int>dist(n,INT_MAX);
            dist[k]=0;

            priority_queue<ip,vector<ip>,greater<ip>>pq;
            pq.push({0,k});

            while(!pq.empty()){
                int f=pq.top().first;
                int s=pq.top().second;
                pq.pop();

                vector<ip>it;
                for(auto it:neighbors[s]){
                    int disUpTo=it.second;
                   // cout<<"disUpTo  "<<disUpTo<<" "<<endl;
                    int nxt=it.first;
                     //cout<<"nxt  "<<nxt<<" "<<endl;
                    if(dist[nxt]>dist[s]+disUpTo){
                        dist[nxt]=dist[s]+disUpTo;
                       // cout<<"dist  "<<dist[nxt]<<" "<<endl;
                        pq.push({dist[nxt],nxt});
                    }
                }
            }
        return pq.top().first;
    }
};