// this has a bug which I dont know how to find
public int networkDelayTime(int[][] times, int N, int K) {
    Map<Integer, Map<Integer,Integer>> adjListWithDistance = new HashMap<>();
    // using this distance Map from K as comparator in priority queue
    Map<Integer, Integer> dMapFromK = new HashMap<>();
    PriorityQueue<Integer> pq = new PriorityQueue<>((k1,k2) -> dMapFromK.get(k1) - dMapFromK.get(k2));
    HashSet<Integer> v = new HashSet<>();
    for(int i = 0; i < times.length; i++){
        int source = times[i][0];
        int dest = times[i][1];
        int dist = times[i][2];
        adjListWithDistance.putIfAbsent(source, new HashMap<>());
        adjListWithDistance.get(source).put(dest, dist);
    }
    dMapFromK.put(K, 0);
    pq.add(K);
    int res = 0;
    while(!pq.isEmpty()){
        int fromNode = pq.poll();
        if(v.contains(fromNode)) continue;
        v.add(fromNode);
        int curDist = dMapFromK.get(fromNode);
        res = curDist;
        if(!adjListWithDistance.containsKey(fromNode)) {
            continue;
        }
        for(Integer toNode: adjListWithDistance.get(fromNode).keySet()){
            if(v.contains(toNode)) continue;
            int toNodeDist = adjListWithDistance.get(fromNode).get(toNode);
            if(dMapFromK.containsKey(toNode) && dMapFromK.get(toNode) <= curDist + toNodeDist){
                continue;
            } else {
                if(!dMapFromK.containsKey(toNode)){
                    dMapFromK.put(toNode, curDist + toNodeDist);
                    pq.offer(toNode);
                } else{
                    dMapFromK.put(toNode, curDist + toNodeDist);
                }
            }
        }
    }
    if(dMapFromK.keySet().size() != N)
        return -1;
    return Collections.max(dMapFromK.values());
}

public final class Solution {
    public static final int networkDelayTime(
        final int[][] times,
        int n,
        final int k
    ) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (final int[] node : times) {
            graph.putIfAbsent(node[0], new HashMap<>());
            graph.get(node[0]).put(node[1], node[2]);
        }
        Queue<int[]> queue = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        queue.add(new int[] {0, k});
        boolean[] visited = new boolean[n + 1];
        int total = 0;
        while (!queue.isEmpty()) {
            int[] curr = queue.remove();
            int currNode = curr[1];
            int currTime = curr[0];
            if (visited[currNode]) {
                continue;
            }
            visited[currNode] = true;
            total = currTime;
            n--;
            if (graph.containsKey(currNode)) {
                for (final int next : graph.get(currNode).keySet()) {
                    queue.add(new int[] {currTime + graph.get(currNode).get(next), next});
                }
            }
        }
        return n == 0 ? total : -1;
    }
}

from typing import List
import heapq
from collections import defaultdict
class Solution:
    def networkDelayTime(self, times: List[List[int]], n, k) -> int:
        queue = [(0, k)]
        graph = collections.defaultdict(list)
        memo = {}
        for u_node, v_node, time in times:
            graph[u_node].append((v_node, time))
        while queue:
            time, node = heapq.heappop(queue)
            if node not in memo:
                memo[node] = time
                for v_node, v_time in graph[node]:
                    heapq.heappush(queue, (time + v_time, v_node))
        return max(memo.values()) if len(memo) == n else -1

// 以下部分可能会微不足道地提高执行时间；
// 可以删除；
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();
// 大多数头文件已经包含；
// 可以删除；
#include <cstdint>
#include <vector>
#include <algorithm>
#define MAX INT_MAX
using ValueType = std::uint_fast16_t;
static const struct Solution {
    static const int networkDelayTime(
        const std::vector<vector<int>>& times, 
        int n, 
        const int k
    ) {
        std::vector<ValueType> distances(n + 1, MAX);
        distances[k] = 0;
        for (ValueType index = 0; index < n; index++) {
            for (const auto& time : times) {
                const ValueType u_node = time[0];
                const ValueType v_node = time[1];
                const ValueType uv_weight = time[2];
                if (distances[u_node] != MAX && distances[v_node] > distances[u_node] + uv_weight) {
                    distances[v_node] = distances[u_node] + uv_weight;
                }
            }
        }
        ValueType total_time = 0;
        for (auto index = 1; index <= n; index++) {
            total_time = std::max(total_time, distances[index]);
        }
        return total_time == MAX ? -1 : total_time;
    }
};