题目描述

小 $C$ 喜欢爬山，但体能有限，不能连续爬升太高。比特峰共有 $n$ 个景点，第 $i$ 个景点海拔为 $h_i$ 米。景点之间共有 $m$ 条双向线路，第 $i$ 条线路连通景点 $u_i$ 与 $v_i$，走这条线路无论方向耗时均为 $t_i$ 分钟。

小 $C$ 在爬山过程中会累积“疲劳值”，初始为 $0$，最大能忍受的疲劳值为 $H$。假设当前小 $C$ 在景点 $x$，存在一条线路通向景点 $y$：

• 若 $h_x > h_y$（下坡），走这条线路会让疲劳值被 清空（变为 $0$）。
• 否则（上坡或持平），走这条线路会使疲劳值增加 $h_y - h_x$。小 $C$ 只能在保证疲劳值不超过 $H$ 的前提下走这条线路。

小 $C$ 从 $1$ 号景点出发，仅能沿给定线路移动。对于每个景点，求从景点 $1$ 出发到达该景点所需的最短时间（分钟），或若不可达则输出 $-1$。

输入格式

输入共 $m+2$ 行：

• 第一行包含三个整数：$n, m, H$，分别表示景点数、线路数和最大疲劳值。
• 第二行包含 $n$ 个整数：$h_1, h_2, \dots h_n$，第 $i$ 个为第 $i$ 个景点的海拔。
• 接下来的 $m$ 行，每行包含三个整数：$u_i, v_i, t_i$，表示一条无向边连接景点 $u_i$ 与 $v_i$，走这条边耗时 $t_i$ 分钟。

输出格式

输出一行，共 $n-1$ 个整数。第 $i$ 个整数表示从景点 $1$ 到达景点 $i+1$ 的最短时间（分钟）；若不可达则输出 $-1$。整数之间以空格分隔。

样例输入 1

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

样例输出 1

1 3 11 16 -1

说明

数据范围

• $2 \le n \le 10^4$，$0 \le m \le 2\times10^4$，$1 \le H \le 100$；
• $1 \le h_i \le 10^9$；
• $1 \le u_i,v_i \le n$，$u_i \ne v_i$；
• $1 \le t_i \le 10^9$。