Network Delay Time (Dijkstra's)

A network has n nodes 1 … n and directed links u v w: a signal sent from u reaches v after w time units. A signal starts at node k. How long until every node has received it? Print -1 if some node never does.

Input:

• line 1: n m k
• next m lines: u v w

Output: the time when the last node receives the signal, or -1.

Constraints: 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5·10⁴, 0 ≤ w ≤ 10⁴; there may be several links between the same pair.

Think about it: this is the largest shortest-path distance from k. All weights are non-negative, so use Dijkstra's algorithm with a min-heap: O((n + m) log n).