## Problem N. Dijkstra ≡

 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 16 Mb Output file: output.txt

### Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

### Input file format

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

### Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

### Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

0.033s 0.008s 15