405012 - 单源最短路径

一个有向图，请输出从某一点出发到所有点的最短路径长度。

第一行包含三个整数n、m、s，分别表示点的个数、有向边的个数和起始点的编号。 随后m行，每行包含三个整数u、v、w，分别表示各有向边的起始点、终点和长度。

一行，包含n个用空格分隔的整数（行末无空格），其中第i个整数表示从起点s出发到终点i的最短路径长度（若s＝i，则最短路径长度为0，若从点s无法到达点i，则最短路径长度为2 147 483 647）。

对于100%的数据：保证数据随机，n≤10 000，m≤500 000。