2551: 地铁费用
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：608
Solved：169
Description
公元8888年，大部分地球居民都迁移至S星球。在S星球，有n个城市，m段高速地铁。地铁是按路程来收费的，举个例子，城市1到城市n的路程是99公里，那么收取99个S币。如果城市1到城市n有多条路径可以选择，按最短那条路来收费。
现在，有一个好人在城市x坐地铁，请问从城市x到其他城市，分别需要花费多少个S币？
（注意：不能到达的城市，不需要任何费用，即费用为0；两个城市之间可以有多条直接相连的地铁，且费用不一样。）
Input
第一行：3个整数n、m、x
接下来m行，每行3个整数a、b、c，表示城市a到城市b的路程是c公里
Output
n行，第i行表示到城市i的费用。
Sample Input Copy
6 5 1
1 2 5
2 3 8
1 4 2
4 5 2
5 3 2Sample Output Copy
0
5
6
2
4
0HINT
5 <= n <= 10000
10 <= m <= 100000
1 <= a、b <= n
1 <= c <= 100
60%的数据：n <= 5000
80%的数据：n <= 8000