GraphDijkstraShortest PathHeap
A network has n nodes labelled 1 to n. Directed links are given as (u, v, w): a signal sent from u reaches v after w time units. A signal starts at node k. Find the time it takes for all nodes to receive it, or -1 if some node can never receive it.
Input
Line 1: n, m and k. Next m lines: u v w.
Output
Print the minimum time for all nodes to receive the signal, or -1.
Constraints
1 <= n <= 100 0 <= m <= 6000 1 <= w <= 100
Example 1
Input
4 3 2 2 1 1 2 3 1 3 4 1
Output
2
Node 4 is reached after 2 units via 2 -> 3 -> 4.