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.
