Tax

JB received his driver's license recently. To celebrate this, JB decides to drive to other cities in Byteland. There are $n$ cities and $m$ bidirectional roads in Byteland, labeled $1,2,\dots,n$. JB starts at city $1$ and can only drive on these $m$ roads. Every city is always reachable from city $1$.

The length of each road is the same, but each road is controlled by one of several engineering companies. For the $i$-th road, the controlling company is $c_i$. If this is the $k$-th time JB drives on a road controlled by company $t$, JB pays $k\times w_t$ dollars in tax.

JB selects a destination city. If the destination is city $k$, JB drives from city $1$ to city $k$ along a shortest path. If several shortest paths exist, JB picks the one with the smallest total tax. Calculate the minimum total tax JB pays for each possible destination.

The input contains only a single case.

The first line contains two integers $n$ and $m$ ($2 \leq n\leq 50$, $n-1\leq m \leq \frac{n(n-1)}{2}$), 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$), the base tax of each company.

Each of the next $m$ lines 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$). This describes a bidirectional road between city $u_i$ and city $v_i$, controlled by company $c_i$.

There is at most one road between any pair of cities, and JB can always drive to every other city.

Print $n-1$ lines. The $k$-th line ($1\leq k\leq n-1$) contains one integer, the minimum number of dollars JB needs to pay when the destination is city $k+1$.