题目描述

Bellman-ford 算法 单源最短路径（弱化版） 给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

输入格式

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。 接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。

输出格式

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31-1。

样例

输入样例 1

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

输出样例 1

0 2 4 3

输入样例 2

5 4 1
1 2 3
2 3 2
3 4 4
4 5 1

输出样例 2

0 3 5 9 10

输入样例 3

6 7 1
1 2 3
1 3 5
3 2 1
3 5 6
2 5 4
2 4 2
5 4 7

输出样例 3

0 3 5 5 7 2147483647

输入样例 4

3 4 1
1 2 10
1 2 3
2 3 5
1 3 20

输出样例 4

0 3 8

输入样例 5

4 5 1
1 1 5
1 2 2
2 3 3
3 4 1
1 4 10

输出样例 5

0 2 5 6