数据结构基础

【题目描述】单源最短路径（path）

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

【输入格式】

第一行包含三个整数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。