2617 - 单源最短路

通过次数

46

提交次数

97

时间限制 : 1 秒
内存限制 : 128 MB

给定一个 n个点,m条有向边的带非负权图,请你计算从 s 出发,到每个点的距离。 到不了的输出-1。

输入

第一行为三个正整数 n,m,s。 第二行起 m 行,每行三个非负整数ui,vi,wi ,表示从 ui到 vi 有一条权值为 wi的有向边。

输出

输出一行 n个空格分隔的整数,表示 s到每个点的距离。

样例

输入

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

输出

0 2 4 3