测试数据来自 system/1695

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出 \(n\) 个顶点，\(m\) 条无向带权边的连通图，和一个出发点（源点）\(s\)：请编程计算 \(s\) 到其他点的最短路径。

【输入格式】

　　第一行：\(n，m\)，为图的顶点数目和边的数目。
　　接下来 \(m\) 行，每行三个整数 \(x,y,t\)，为一条边关联的两个顶点和边的权值。
　　最后一行一个整数 \(s\)。

【输出格式】

　　共 \(n\) 行，每行 1 个整数，第 \(i\) 行的整数表示从 \(s\) 到顶点 \(i\) 的最短路径长度。

【输入输出样例】

　Input

5 6
1 2 1
1 3 3
2 4 2
2 3 1
1 5 8
4 3 2
1

　Output

0
1
2
3
8

【数据限制】

　　\(100\%\) 的数据满足，\(n≤50000\)， \(m≤100000\)，\(0<t≤100\)。

【来源】

　　Mr.he