def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        # Dijkstra's Algorithm (Single-Source Shortest Path):
        # We want the minimum time for a signal sent from node k
        # to reach all n nodes in a directed graph with non-negative weights.
        
        # Key Ideas:
        #   1. Model the network as a directed weighted graph.
        #   2. Use a min-heap to always expand the node with the smallest
        #      known signal arrival time.
        #   3. Maintain a dictionary of shortest known times to each node.
        #   4. If all nodes are reached, return the maximum of these times.
        #   5. If some node is unreachable, return -1.

        # Build adjacency list: graph[src] = [(dest, weight), ...]
        # tc: O(edge)
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # Min-Heap:
        # Each entry is (time_to_reach_node, node)
        # sc: O(node)
        heap = [(0, k)]
        
        # Dictionary to track shortest known time to each node
        # Invariant: once a node is added here, its shortest time is finalized
        shortest_time = {}
        
        # tc: each node/edge O(e) processed via O(log n) heap operations O(e log n)
        while heap:

            # Pop node with smallest known arrival time
            time, node = heapq.heappop(heap)
            
            # Skip if this node already has a finalized shortest time
            # (We found a better path earlier)
            if node in shortest_time:
                continue
            
            # Record shortest time to reach this node
            shortest_time[node] = time
            
            # Explore Choices:
            # Relax all outgoing edges from this node
            for neighbor, wt in graph[node]:

                # If neighbor not finalized, push updated time candidate
                if neighbor not in shortest_time:
                    heapq.heappush(heap, (time + wt, neighbor))
        
        # After processing:
        # If not all nodes were reached, signal cannot reach everyone
        if len(shortest_time) != n:
            return -1
        
        # Result:
        # The total network delay is the maximum shortest arrival time
        res = max(shortest_time.values())

        # overall: tc O(e log n)
        # overall: sc O(n + e)     
        return res