eolymp
bolt
Try our new interface for solving problems
Problems

Shortest Paths

Shortest Paths

Time limit 1 second
Memory limit 128 MiB

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 (2n2000, 1m5000) - 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
-
-
-
*
Source 2005 Petrozavodsk, Andrew Stankevich Contest 13, August 24, Problem E