AT_abc463_e [ABC463E] Roads and Gates

给定一个 $N$ 个结点 $M+\dfrac{N(N-1)}{2}$ 条边的无向图。结点编号 $1 \sim N$。 图中的边有以下两种类型： + 对于所有 $1 \le i \le M$，存在一条结点 $u_i$ 和结点 $v_i$ 之间的边权为 $T_i$ 的无向边。 + 对于所有 $1 \le i < j \le N$，存在一条结点 $i$ 和结点 $j$ 之间的边权为 $X_i+X_j+Y$ 的无向边。 对于所有 $2 \le k \le n$，求出结点 $1$ 至结点 $k$ 的最短路径长度。

第一行 $3$ 个整数 $N,M,Y$。 接下来 $M$ 行，第 $i$ 行 $3$ 个整数 $u_i,v_i,T_i$。 最后一行 $N$ 个整数 $X_1,X_2,\cdots,X_n$。

一行 $n-1$ 个整数，第 $i$ 个整数为 $k=i+1$ 的答案。

### 样例 1 解释 对于结点 $7$，路径 $1 \to 2 \to 7$ 的长度为 $7$，且不存在 $1 \to 7$ 的长度 $< 7$ 的路径，所以 $k=7$ 时答案为 $7$。 ### 样例 2 解释 答案可能 $\ge 2^{31}$。 ### 数据范围 + $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 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$