JB 最近拿到了驾照。为了庆祝，JB 决定开车去 Byteland 的其他城市。Byteland 有 $n$ 个城市和 $m$ 条双向道路，编号为 $1, 2, \dots, n$。JB 目前在第 $1$ 号城市，他只能在这些 $m$ 条道路上行驶。保证 JB 可以从第 $1$ 号城市到达 Byteland 的任意其他城市。

每条道路的长度相同，但它们由不同的工程公司控制。对于第 $i$ 条边，它由第 $c_i$ 号公司控制。如果这是 JB 第 $k$ 次经过由第 $t$ 号公司控制的边，JB 需要支付 $k \times w_t$ 美元的税费。

JB 正在选择他的目的地。假设目的地是第 $k$ 号城市，他将沿着最短路径从第 $1$ 号城市行驶到第 $k$ 号城市，并在存在多条最短路径时，使总税费最小化。请编写一个程序，帮助 JB 计算前往每个可能目的地时他需要支付的最小美元金额。

输入格式

输入包含单个测试用例。

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 50, n - 1 \le m \le \frac{n(n-1)}{2}$)，分别表示城市数量和双向道路数量。

第二行包含 $m$ 个整数 $w_1, w_2, \dots, w_m$ ($1 \le w_i \le 10\,000$)，表示每家公司的基础税费。

接下来的 $m$ 行中，第 $i$ 行 ($1 \le i \le m$) 包含三个整数 $u_i, v_i$ 和 $c_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le c_i \le m$)，表示连接第 $u_i$ 号城市和第 $v_i$ 号城市的一条双向道路，由第 $c_i$ 号公司控制。

保证任意两个城市之间最多只有一条道路，且保证 JB 可以到达所有其他城市。

输出格式

输出 $n - 1$ 行，第 $k$ 行 ($1 \le k \le n - 1$) 包含一个整数，表示当目的地为第 $(k + 1)$ 号城市时，JB 需要支付的最小美元金额。

样例

输入 1

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

输出 1

1
9
1
3