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

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 1015 by absolute value. Graph can contain multiple edges and loops.

Output

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 "-".