2551: 地铁费用

公元8888年，大部分地球居民都迁移至S星球。在S星球，有n个城市，m段高速地铁。地铁是按路程来收费的，举个例子，城市1到城市n的路程是99公里，那么收取99个S币。如果城市1到城市n有多条路径可以选择，按最短那条路来收费。 现在，有一个好人在城市x坐地铁，请问从城市x到其他城市，分别需要花费多少个S币？ （注意：不能到达的城市，不需要任何费用，即费用为0；两个城市之间可以有多条直接相连的地铁，且费用不一样。）

第一行：3个整数n、m、x 接下来m行，每行3个整数a、b、c，表示城市a到城市b的路程是c公里

n行，第i行表示到城市i的费用。

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

0
5
6
2
4
0