class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
    {
            //next time when u come around this problem check the wrong ans once

           	//dijkstra: suppose we are at a node and we see that a node(v) from that node have 
           	//dist[v]>dist[u]+wt(u->v) now we should not mark the node v as visited and restrict 
           	//further choices of dist[v] being more smaller from other nodes

           	//In dijkstra we mark a node visited only when it is popped out of the queue
           	//U NEED TO UNDERSTAND THE DIFFERENT CASES ON WHERE WE MARK VIS=true

           	//S---4-->X
           	//\     /
           	// 2   1
           	//  \ /
           	//   W

           	//consider this case for clarity: here first we pick 2 and mark vis[W]=true then we have wt=4
           	//so we mark vis[X]=true and put both of them in the queue now when we get[2,W] from the pQ
           	//we see tht dist[X]=4 >dist[W]+1 so we update dist[X] to 3 but as we have marked it visited 
           	//so we do not push it again in the pQ-->this is WRONG!!!
           	//as we won't get any shortest paths which wd pass through X in the later graph

           	//once we mark a node as visited we are certain that we have got the shortest path till that                 point
           	//so we do not check for further possibilities later.
        vector<vector<pair<int,int>>>graph(n+1);
        vector<int>dist(n+1,1e9);
        vector<bool>vis(n+1,0);
        dist[k]=0;
        for(auto &t:times)
        {
            graph[t[0]].push_back({t[1],t[2]});
        }
        
        priority_queue<pair<int,int>>pQ;
        
        pQ.push({0,k});
        vis[k]=1;
        
        int res=0;
        while(!pQ.empty())
        {
            auto [wt,node]=pQ.top();
            pQ.pop();
            
            wt*=-1;
            vis[node]=1;
            for(auto &[v,d]:graph[node])
            {
               if(!vis[v]&&wt+d<dist[v])
               {
                dist[v]=wt+d;
                pQ.push({-dist[v],v}); 
               }
            }
        }
        
        for(int i=1;i<=n;i++)
        {
            if(dist[i]==1e9)
            return -1;
        else
            res=max(res,dist[i]);
         }
    
        return res;
    }
};