题目描述

AtCoder 国有 $N$ 座城市和 $M$ 条道路。第 $i$ 条道路 $(1 \le i \le M)$ 双向连接城市 $u_i$ 和城市 $v_i$，从一端走到另一端需要 $T_i$ 分钟。

此外，每座城市都装有一台传送门。使用传送门，可以从城市 $i$ $(1 \le i \le N)$ 直接到达城市 $j$ $(1 \le j \le N)$，耗时 $X_i + X_j + Y$ 分钟。

除此之外，没有别的方式在城市之间移动。

对每个 $k = 2, 3, \ldots, N$，请回答下面的问题：

• 从城市 $1$ 走到城市 $k$，最少需要多少分钟？

其中，在同一座城市里从一条道路（或传送门）换乘到另一条道路（或传送门）的时间可以忽略不计。

输入格式

N M Y
u_1 v_1 T_1
u_2 v_2 T_2
...
u_M v_M T_M
X_1 X_2 ... X_N

输出格式

在一行中依次输出 $k = 2, 3, \ldots, N$ 的答案，相邻两个数之间用一个空格隔开。

输入示例 1

7 7 3
1 2 1
1 3 6
2 3 4
3 5 8
3 7 4
4 5 2
4 7 9
3 1 4 1 5 9 2

输出示例 1

1 5 6 8 14 7

示例 1 说明

以 $k = 7$ 为例，可以用 $7$ 分钟从城市 $1$ 到城市 $7$：

• 走第 $1$ 条道路，花 $1$ 分钟从城市 $1$ 到城市 $2$；
• 再用传送门，花 $X_2 + X_7 + Y = 1 + 2 + 3 = 6$ 分钟从城市 $2$ 到城市 $7$。

合计 $1 + 6 = 7$ 分钟。可以证明不存在 $6$ 分钟以内的走法，所以 $k = 7$ 的答案是 $7$。

输入示例 2

2 0 1000000000
1000000000 1000000000

输出示例 2

3000000000

示例 2 说明

这里一条道路都没有（$M = 0$），只能用传送门，耗时 $X_1 + X_2 + Y = 10^9 + 10^9 + 10^9 = 3 \times 10^9$。

请注意答案可能达到 $2^{31}$ 以上，必须用 64 位整数（long long）存储。

输入示例 3

12 20 873
2 7 940
6 9 444
6 11 809
7 8 786
9 10 468
7 10 234
6 10 660
4 12 939
8 10 896
1 11 953
8 10 818
4 8 967
3 9 724
6 7 929
3 4 948
1 3 999
10 11 724
7 10 338
1 8 967
1 12 733
581 978 950 629 583 729 554 712 438 930 774 279

输出示例 3

2432 999 1672 2037 1762 1753 967 1723 1677 953 733

示例 3 说明

注意有些城市走道路更划算（如 $k = 3$ 直接走第 $16$ 条道路只要 $999$ 分钟），有些城市则是先走一段道路再传送更划算。答案是两类走法混合后的最小值。

约束条件

• $2 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le u_i < v_i \le N \ (1 \le i \le M)$
• $1 \le T_i \le 10^9 \ (1 \le i \le M)$
• $1 \le X_i \le 10^9 \ (1 \le i \le N)$
• $1 \le Y \le 10^9$
• 所有输入值均为整数