有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, K, X, M, S。
接下来M行，每行输入三个整数 a_i, b_i, c_i ，表示城市 a_i 和 b_i 之间有新建道路，长度为 c_i 。
保证不存在由一个城市连向自己的道路，所有道路两两不同，且任意城市间两两可达。

2 \le N \le 10^5, \ 2 \le K \le N,\  1 \le X \le 10^9,\  0 \le M \le 10^5, 1 \le S \le N,\ 1 \le a_i, b_i \le N, a_i \ne b_i,\ 1 \le c_i \le 10^9

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