31144번 - Tax 다국어

문제

JB received his driver's license recently. To celebrate this fact, JB decides to drive to other cities in Byteland. There are $n$ cities and $m$ bidirectional roads in Byteland, labeled by 1,2,ドル\dots,n$. JB is at the 1ドル$-st city, and he can only drive on these $m$ roads. It is always possible for JB to reach every city in Byteland.

The length of each road is the same, but they are controlled by different engineering companies. For the $i$-th edge, it is controlled by the $c_i$-th company. If it is the $k$-th time JB drives on an edge controlled by the $t$-th company, JB needs to pay $k\times w_t$ dollars for tax.

JB is selecting his destination city. Assume the destination is the $k$-th city, he will drive from city 1ドル$ to city $k$ along the shortest path, and minimize the total tax when there are multiple shortest paths. Please write a program to help JB calculate the minimum number of dollars he needs to pay for each possible destination.

입력

The input contains only a single case.

The first line of the input contains two integers $n$ and $m$ (2ドル \leq n\leq 50,ドル $n-1\leq m \leq \frac{n(n-1)}{2}$), denoting the number of cities and the number of bidirectional roads.

The second line contains $m$ integers $w_1,w_2,\dots,w_m$ (1ドル\leq w_i\leq 10,000円$), denoting the base tax of each company.

In the next $m$ lines, the $i$-th line $(1 \le i \le m)$ contains three integers $u_i,v_i$ and $c_i$ (1ドル\leq u_i,v_i\leq n,ドル $u_i\neq v_i,ドル 1ドル\leq c_i\leq m$), denoting denoting an bidirectional road between the $u_i$-th city and the $v_i$-th city, controlled by the $c_i$-th company.

It is guaranteed that there are at most one road between a pair of city, and it is always possible for JB to drive to every other city.

출력

Print $n-1$ lines, the $k$-th (1ドル\leq k\leq n-1$) of which containing an integer, denoting the minimum number of dollars JB needs to pay when the destination is the $(k+1)$-th city.

제한

힌트