# Shortest Paths

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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

Input #1

Answer #1

Submissions 3K

Acceptance rate 18%