Shortest Path

Given a directed graph and a starting vertex K, compute the shortest distance from K to every vertex. Every edge has an integer weight from 1 to 10.

The first line contains the number of vertices V and the number of edges E. The constraints are 1 <= V <= 20,000 and 1 <= E <= 300,000. Vertices are numbered from 1 through V.

The second line contains the starting vertex K, where 1 <= K <= V.

Each of the next E lines contains three integers u, v, and w. This represents a directed edge from u to v with weight w. The two endpoints are different, and w is an integer from 1 to 10. There may be multiple edges between the same ordered pair of vertices.

Print V lines. On the i-th line, print the shortest distance from K to vertex i. Print 0 for the starting vertex itself. If vertex i is unreachable from K, print INF.