You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

&nbsp;
Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2


Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1


Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1


&nbsp;
Constraints:


	1 &lt;= k &lt;= n &lt;= 100
	1 &lt;= times.length &lt;= 6000
	times[i].length == 3
	1 &lt;= ui, vi &lt;= n
	ui != vi
	0 &lt;= wi &lt;= 100
	All the pairs (ui, vi) are unique. (i.e., no multiple edges.)


import heapq
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        adjlist = [[] for _ in range(n+1)]
        
        for src, dst, weight in times:
            adjlist[src].append((dst, weight))
        
        visited = [-1]*(n+1)
        captured =[-1]*(n+1)

        priority_queue = [(0,k)]
    
        nums = 0
        total_dist = 0
        
        while priority_queue:

            dst, node = heapq.heappop(priority_queue)

            if captured[node] != -1:
                continue
            captured[node] = dst
            
            nums += 1
            total_dist = dst
            
            for nbr,wt in adjlist[node]:
                if captured[nbr] == -1:
                    heapq.heappush(priority_queue,(captured[node]+wt, nbr))
        if nums == n:
            return total_dist
        else:
            return -1
class Solution {
    HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
    public int networkDelayTime(int[][] times, int n, int k) {
        for (int i = 1; i <= n; i++) {
            map.put(i, new HashMap<>());
        }
        for (int i = 0; i < times.length; i++) {
            map.get(times[i][0]).put(times[i][1], times[i][2]);
        }
        int ans = BFS(k, n);

        return ans == 1000 ? -1 : ans;
    }
    public int BFS(int k, int n) {
        LinkedList<Integer> queue = new LinkedList<>();

        int[] timeReach = new int[n + 1];
        Arrays.fill(timeReach, 1000);
        timeReach[0] = 0;

        timeReach[k] = 0;

        queue.add(k);

        while (!queue.isEmpty()) {
            int rv = queue.remove();
            for (int nbrs : map.get(rv).keySet()) {
                int t = map.get(rv).get(nbrs) + timeReach[rv];
                if (t < timeReach[nbrs]) {
                    timeReach[nbrs] = t;
                    queue.add(nbrs);
                }
            }
        }

        int time = 0;

        for (int i : timeReach) {
            time = Math.max(i, time);
        }

        return time;
    }
}
class cmp{
  public:
    bool operator()(pair<int,int> &a,pair<int,int> &b)
    {
        return a.second>b.second;
    }
};

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<pair<int,int>> a[n];
        for(auto it:times)
        {
            a[it[0]-1].push_back({it[1]-1,it[2]});
        }

        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
        vector<int> dist(n,1e7);

        pq.push({k-1,0});

        vector<int> vis(n,0);
        while(pq.size())
        {
            auto curr = pq.top();
            pq.pop();

            int v = curr.first;
            int w = curr.second;

            if(vis[v])continue;

            vis[v] = 1;
            dist[v] = w;
            for(auto it:a[v])
            {
                if(vis[it.first]==0)
                {
                    pq.push({it.first,it.second + w});
                }
            }
        }

        int mx = INT_MIN;
        for(auto it:dist)
            mx = max(mx,it);

        if(mx>=1e7)return -1;
        return mx;

    }
};
/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */

let visited,edges,dijkastra_arr,min_heap
const MAX_VALUE=Math.pow(10,6);

const dijkastra=(source)=>{
    visited[source]=true;
    min_heap.pop();
    let nei=edges[source]||[];
    // if(!nei.length)return;
    for(let i=0;i<nei.length;i++){
        let[src,dst,t]=nei[i];
        if(visited[dst])continue;
        let time_till_src=dijkastra_arr[src];
        if(time_till_src>=MAX_VALUE)continue;
        let time_till_dst=time_till_src+t;
        dijkastra_arr[dst]=Math.min(dijkastra_arr[dst],time_till_dst);
    }
    min_heap.sort((a,b)=>{
        return dijkastra_arr[b]-dijkastra_arr[a];
    });
    if(min_heap.length && dijkastra_arr[min_heap[min_heap.length-1]]<MAX_VALUE)
    dijkastra(min_heap[min_heap.length-1]);

}
var networkDelayTime = function(times, n, k) {
    visited=[];
    edges={};
    dijkastra_arr=[];
    min_heap=[];

    for(let i=0;i<times.length;i++){
        if(!edges[times[i][0]])edges[times[i][0]]=[];
        edges[times[i][0]].push(times[i]);
    }
    // console.log(edges,"edges")
    for(let i=0;i<=n;i++){
        if(i===0){//cz numbes are starting from One
            visited[i]=true;
            dijkastra_arr[i]=-1;
            min_heap[i]=i;
        }else{
                  min_heap[i]=i;
        dijkastra_arr[i]=MAX_VALUE;
        visited[i]=false;
        }

    }

    dijkastra_arr[k]=0;
    min_heap.sort((a,b)=>{
        return dijkastra_arr[b]-dijkastra_arr[a];
    });
    min_heap.pop();//For removing zeroth entry;
    dijkastra(k);
    let max_time=0;
    if(min_heap.length)return -1;
        for(let i=0;i<dijkastra_arr.length;i++){
            max_time=Math.max(dijkastra_arr[i],max_time);
    }
    return max_time;
};
Network Delay Time