给你一个简单连接的无向图，有 N 个顶点和 M 条边。每个顶点 i\,(1\leq i \leq N) 的权重为 A_i 。每条边 j\,(1\leq j \leq M) 双向连接顶点 U_j 和 V_j ，权重为 B_j 。
该图中路径的权重定义为路径上出现的顶点和边的权重之和。
针对每个 i=2,3,\dots,N 求解以下问题：
- 找出从顶点 1 到顶点 i 的路径的最小权重。
第一行两个数字，N 个顶点和 M 条边
第二行，每行N 个顶点的权重，a_1,a_2,\dots,a_n
接下来M 行，每行三个数字u,v,w分别表示从$u$到$v$有一个$w$的边
将 disi=2,3,\dots,N 的最小权重输出并用空格隔开。
3 3 1 2 3 1 2 1 1 3 6 2 3 2
4 9
2 1 0 1 1 2 3
4
5 8 928448202 994752369 906965437 942744902 907560126 2 5 975090662 1 2 908843627 1 5 969061140 3 4 964249326 2 3 957690728 2 4 942986477 4 5 948404113 1 3 988716403
2832044198 2824130042 4696218483 2805069468
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq U_j < V_j \leq N
- (U_i, V_i) \neq (U_j, V_j) 如果 i \neq j .
- 图是连通的。
- 0 \leq A_i \leq 10^9
- 0 \leq B_j \leq 10^9
- 所有输入值均为整数。