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

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

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