Shortest Paths

Giriş

The first line contains three integers $n$, $m$, $s$ (2 \leq n \leq 2000, 1 \leq m \leq 5000): the number of vertices and edges in the graph, and the starting vertex number.

The next $m$ lines describe the edges of the graph. Each edge is given by three integers: the starting vertex, the ending vertex, and the weight of the edge. The weight is an integer, and its absolute value does not exceed 10^{15}. The graph may contain multiple edges and loops.

Çykyş

Print $n$ lines: for each vertex $u$, print the length of the shortest path from $s$ to $u$. If there is no path between $s$ and $u$, print "*". If there is no shortest path between $s$ and $u$, print "-".

Mysallar