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

---

【题目描述】

　　给出 \(N\) 个顶点，\(M\) 条无向带权边的连通图，请编程计算从 \(S\) 到各点最大边最小的路径。

【输入格式】

　　第一行：\(N，M\)，为图的顶点数目和边的数目。
　　接下来 \(M\) 行，每行三个整数 \(x,y,t\)，为一条边关联的两个顶点和边的权值（权值是 0..10000 之间的整数）。
　　最后一行一个整数 \(S\)。

【输出格式】

　　共 \(N-1\) 行，每行 1 个整数，第 \(i\) 行的两个整数分别表示从 \(S\) 到顶点 \(i(i!=S)\) 的最大边的最小值。

【输入输出样例】

　Input

5 7
1 5 1
1 2 4
2 3 2
2 4 5
3 4 7
3 5 3
4 5 6
1

　Output

3
3
5
1

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤50000\)，\(1≤M≤100000\)。

【来源】

　　Mr.he