一个有向图，请输出从某一点出发到所有点的最短路径长度。
第一行包含三个整数n、m、s，分别表示点的个数、有向边的个数和起始点的编号。 随后m行，每行包含三个整数u、v、w，分别表示各有向边的起始点、终点和长度。
一行，包含n个用空格分隔的整数（行末无空格），其中第i个整数表示从起点s出发到终点i的最短路径长度（若s＝i，则最短路径长度为0，若从点s无法到达点i，则最短路径长度为2 147 483 647）。
4 6 1 1 2 3 2 3 4 2 4 5 1 3 6 3 4 7 1 4 8
0 3 6 8
对于100%的数据：保证数据随机，n≤10 000，m≤500 000。
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |