Read a directed graph with non-negative integer weights and a source s, and print the shortest distance from s to every vertex.
Input
n m s // vertices 0 .. n-1, number of edges, source
u1 v1 w1 // m lines: directed edge u -> v with weight w (0 <= w <= 2,000,000,000)
...
Parallel edges are allowed.
Output — one line per vertex, in increasing vertex order: v: d, or v: INF if v cannot be reached from s. For
6 10 0
0 4 7
0 3 2
3 4 3
3 1 8
4 1 1
3 5 10
1 5 2
5 2 3
1 2 6
4 2 12
the output is
0: 0
1: 6
2: 11
3: 2
4: 5
5: 8
Use a PriorityQueue (lazy deletion is fine). Distances can exceed the int range, so use long.