该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

从前有 $m$ 家公司，编号从 $1$ 到 $m$ ，每家公司存在系数 $x_i$ 。

有一张 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边连接 $u_i,v_i$ ，被公司 $c_i$ 所控制。

每经过一条边时，你需要向公司支付费用：

如果这是第 $k$ 次经过公司 $i$ 所控制的边，你就需要支付 $kx_i$ 的费用。

现在对于 $t\in [2,n]$ ，你希望求出一条从 $1$ 到 $t$ 的路径，

使得在走的边数最少的前提下最小化支付的费用。

输入格式

第一行包含两个整数 $n,m$ ，$n$ 表示无向图的点数，$m$ 表示边数和公司的个数。

第二行包含 $m$ 个整数，表示 $x_1,x_2,\dots,x_m$ 。

接下来 $m$ 行，每行三个整数 $u_i,v_i,c_i$ ，表示边 $i$ 的两个顶点以及控制它的公司。

输出格式

你需要输出 $n-1$ 行，其中第 $i$ 行输出一个整数，表示 $1$ 到 $i+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
9
1
3

数据范围

对于所有数据，$1\le n\le 50,n-1\le m\le \tbinom{n}{2},1\le x_i\le 10000,1\le u_i,v_i\le n,u_i\neq v_i,1\le c_i\le m$ 。保证不存在两条边连接的点对相同。不存在自环。保证图是连通的。

子任务 1 ( 20% ) : $n\le 10$ 。

子任务 2 ( 30% ) : $n\le 20$ 。

子任务 3 ( 20% ) : $n\le 30$ 。

子任务 4 ( 30% ) : 无特殊限制。