# https://leetcode.com/problems/network-delay-time
import heapq

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n)]
        for src, dst, time in times:
            graph[src-1].append((dst-1, time))

        dists = [float('inf')]*n

        q = [(0, k-1)]
        while q:
            dist, v = heapq.heappop(q)
            if dists[v] < float('inf'):
                continue
            dists[v] = dist
            for u, distvu in graph[v]:
                if dists[u] == float('inf'):
                    heapq.heappush(q, (dist + distvu, u))

        maxDist = max(dists)
        return -1 if float('inf') == maxDist else maxDist