4470 - 第十课:团间距离

有N座城市,编号为1到N。城市间由双向道路连通。
编号为1到K的城市都是古城,这些城市两两由长度为X的双向道路连接,共有$ \frac{K*(K-1)}{2}$条这样的道路。
此外,还有M条新建的道路,长度不一定相同,其中第i条链接了编号为$ a_i $和$ b_i $的城市,长度为$ c_i $。
不存在由一个城市连向自己的道路。所有道路(共$ M + \frac{K*(K-1)}{2} $条)两两不同。保证可以从一个城市出发,经由城市间的双向道路,到达任意一个其它城市。
现在想要计算一下从城市S出发,到达其它每个城市的最短路径各是多少。
 

输入

第一行输入五个整数$ N(2 \le N \le 10^5), K(2 \le K \le N), X(1 \le X \le 10^9)M(0 \le M \le 10^5), S(1 \le S \le N) $。
接下来M行,每行输入三个整数$ a_i, b_i(1 \le a_i, b_i \le N, a_i \ne b_i), c_i(1 \le c_i \le 10^9) $,表示城市$ a_i $和$ b_i $之间有新建道路,长度为$ c_i $。
保证不存在由一个城市连向自己的道路,所有道路两两不同,且任意城市间两两可达。
 

输出

输出一行,包含N个整数,第i个整数代表从编号S的城市到编号为i的城市的最短路径长度。从编号为S的城市到自身的距离为0。
 

样例

输入

5 4 100 2 3
1 5 50
5 3 160

输出

100 100 0 100 150
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题