题目描述
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入
第一行包含三个整数n,m,s，（1 ≤ n ≤ 100000，1 ≤ m ≤ 200000）分别表示点的个数、有向边的个数、出发点的编号。
接下来m行每行包含三个整数u,v,w，表示一条u→v的，长度为w的边。（1 ≤ w ≤ 1000）保证从起点出发能到达所有其他点。
输出
输出一行n个整数，第i个表示s到第i个点的最短路径。
样例输入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4样例输出
0 2 4 3