• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i] = (uᵢ, vᵢ, wᵢ) with 1 <= wᵢ <= 100
• Links are directed — a link from u to v does not imply one from v to u
• All weights are positive, so Dijkstra's greedy assumption holds

The wording describes a signal spreading through a network, but the two questions hiding inside it are ordinary ones. First: when does each node receive the signal? Second: how do those individual answers combine into one?

The signal leaves node k and travels along every outgoing link at once. When it reaches a node, that node immediately rebroadcasts along all of its own outgoing links.

So a node may be reached by several different routes, at several different times — and the arrival that matters is the earliest one, because once a node has the signal, later copies change nothing.

That phrasing is the entire translation. "Earliest arrival time at each node" is exactly "shortest path from the source to each node", with link delays as edge weights. Nodes are vertices, links are directed weighted edges, and the propagation is a single-source shortest-path computation.

Now the second question, which is where people go wrong. Having computed every node's earliest arrival, what is the answer?

Not the sum. The signal is not carried from node to node in sequence by a single messenger — it spreads everywhere in parallel, so the delays overlap rather than accumulate. The network is fully informed at the moment the last node hears it, so the answer is the maximum over all arrival times.

And if any node's arrival is infinite, it is never reached at all, so the answer is -1. Note this must be checked against every node from 1 to n, including nodes that appear nowhere in the link list — an isolated node is unreachable and must produce -1.

Since every weight is positive, the greedy approach applies: repeatedly settle the unsettled node with the smallest known arrival time, and that time is final.

The justification is worth being able to give. Suppose u is the unsettled node with the smallest tentative arrival d, and imagine some faster route to u exists. That route begins at the settled source and ends at unsettled u, so it must pass through some first unsettled node x, whose tentative time is already at least d by the choice of u. The rest of the route from x to u has non-negative weight, so the total is at least d. No faster route exists. Non-negativity is precisely what makes that last step valid.

Keeping the smallest tentative time available needs a min-heap, whose top element is always the minimum and whose operations cost O(log n).

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))                 # directed: only one direction

    arrival = {}
    heap = [(0, k)]                           # (time, node)

    while heap:
        t, node = heapq.heappop(heap)
        if node in arrival:
            continue                          # already settled at an earlier time
        arrival[node] = t
        for nxt, w in adj[node]:
            if nxt not in arrival:
                heapq.heappush(heap, (t + w, nxt))

    if len(arrival) < n:
        return -1                             # some node never received it
    return max(arrival.values())

Cost: each link pushes at most one heap entry, so O(E log V) time and O(V + E) space. With n at 100 and 6000 links this is negligible — Bellman-Ford's O(V × E), around 600,000 operations, would also pass comfortably and is easier to write correctly under pressure.

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2.

Adjacency: node 2 points to node 1 with weight 1 and to node 3 with weight 1; node 3 points to node 4 with weight 1. Nodes 1 and 4 have no outgoing links.

Four nodes settled out of four, so nothing is unreachable. Arrivals are 0, 1, 1 and 2, and the maximum is 2. Nodes 1 and 3 were informed simultaneously at time 1 — the delays ran in parallel, which is why the answer is 2 rather than 0 + 1 + 1 + 1.

Now times = [[1,2,1]], n = 2, k = 2. The adjacency list has node 1 pointing at node 2, and node 2 pointing nowhere. The heap starts as [(0, 2)], pops it, settles arrival[2] = 0, and finds no outgoing links. The heap empties with only one node settled out of two, so the answer is -1. Node 1 has a link to the source, which does nothing — directed edges only carry signal one way.

Two habits are worth taking from this.

The first is translation. Delay, latency, travel time, cost, distance are all the same thing to a shortest-path algorithm. The story changes; the graph does not. Once the mapping is stated — nodes are vertices, links are directed weighted edges, arrival time is shortest-path distance — the problem is a standard one.

The second is the aggregation step, which is where the actual thinking lives. Computing all the distances is routine; deciding what to do with the resulting table is what varies. Here the answer is the maximum, because parallel propagation finishes when the slowest branch finishes. A different question over identical distances — the average latency, the count of nodes within some threshold, the nearest server — needs a different reduction over the same table.

Train the reflex: when something spreads through a network and you are asked how long until everything is covered, compute each node's earliest arrival and take the maximum. The word "until everything" almost always means a maximum over shortest paths, never a sum.