## Problem F. Fast Dijkstra ≡

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

### Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed 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 arcs.

### Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

### Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

### Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 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.038s 0.009s 15