Problems
Shortest Paths
Shortest Paths
The weighted oriented graph and its vertex s are given. For each vertex u print the length of the shortest path from s to u.
Input data
The first line contains three integers n, m, s (2 ≤ n ≤ 2000, 1 ≤ m ≤ 5000) - the number of vertices, edges and the number of the starting vertex.
Next m lines describe the graph edges. Each edge is given with three numbers - the starting vertex, the destination vertex and the weight of the edge. The weight is an integer not greater than 10^15
by absolute value. Graph can contain multiple edges and loops.
Output data
Print n lines - for each vertex u print the length of the shortest path from s to u. If the path does not exist between s and u, print "\*". If the shortest path between s and u does not exist, print "-".
Examples
Input example #1
6 7 1 1 2 10 2 3 5 1 3 100 3 5 7 5 4 10 4 3 -18 6 1 -1
Output example #1
0 10 - - - *