题目描述

强哥给他的学生上完课之后，终于有时间去度假啦！

强哥计划去 Russland 旅游，并且他已经获取了 Russland 的道路交通地图。

Russland 总共有 $N$ 座城市和 $M$ 条连通这些城市的双向道路。强哥的旅行计划是这样的：

1. 他会先抵达 $1$ 号城市，即
2. 他会选择一座结束旅游的城市 $x$，但是一定不是 $1$ 号。
3. 他会选择一条路径，路径上的每条道路都会有交通费，而路径上经过的每一座城市（包括 $1$ 和 $x$）强哥都会在那住一晚上，自然有旅店的费用。
4. 路径条数可能会很多，强哥会选择其中最便宜的那条。

强哥希望你能帮忙把 $x$ 取 $2\sim N$ 时的最便宜价格全部算出来。如果你正确地算出来，就能免费跟着他去旅游。

输入格式

第一行为两个数 $N,M$。

第二行为 $N$ 个数，表示在每座城市过夜花的钱。

往后 $M$ 行，每一行有三个数 $U,V,B$，其中前两个数是道路两端的编号，第三个数是路费。

输出格式

一行 $N-1$ 个数，依次表示 $x$ 取 $2\sim 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$
• $i\neq\ j$ なら $(U_i,V_i)\ \neq\ (U_j,V_j)$
• 图是连通的
• $0\ \leq\ A_i\ \leq\ 10^9$
• $0\ \leq\ B_j\ \leq\ 10^9$
• 输入的所有数都是整数