Network Delay Time

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    g = collections.defaultdict(lambda: collections.defaultdict(int))

    for u, v, w in times:
        g[u][v] = w

    dists = {i: float('inf') for i in range(1, n + 1)}
    dists[k] = 0

    q = [(0, k)]

    while q:
        inc, u = heapq.heappop(q)

        for v, cost in g[u].items():
            if inc + cost >= dists[v]:
                continue

            dists[v] = inc + cost
            heapq.heappush(q, (inc + cost, v))

    mx = max(dists.values())
    return -1 if mx == float('inf') else mx

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    g = collections.defaultdict(lambda: collections.defaultdict(int))

    for u, v, w in times:
        g[u][v] = w

    q = [(0, k)]  # inc, node
    res = -1
    visited = set()

    while q:
        inc, u = heapq.heappop(q)
        if u not in visited:
            res = inc

        visited.add(u)

        for v, cost in g[u].items():
            if v in visited:
                continue

            heapq.heappush(q, (inc + cost, v))

    return res if len(visited) == n else -1