세금

JB는 최근 운전면허를 땄다. 이를 기념해 JB는 Byteland의 다른 도시들로 차를 몰고 가기로 했다. Byteland에는 $n$개의 도시와 $m$개의 양방향 도로가 있고, 도시는 $1,2,\dots,n$으로 번호가 매겨져 있다. JB는 1번 도시에서 출발하며, 이 $m$개의 도로로만 이동할 수 있다. 어떤 도시든 항상 1번 도시에서 도달할 수 있다.

각 도로의 길이는 모두 같지만, 도로마다 관리하는 엔지니어링 회사가 다르다. $i$번 도로는 $c_i$번 회사가 관리한다. JB가 $t$번 회사가 관리하는 도로를 $k$번째로 지날 때마다 세금으로 $k\times w_t$달러를 낸다.

JB는 목적지 도시를 고른다. 목적지가 $k$번 도시라면 JB는 1번 도시에서 $k$번 도시까지 최단 경로를 따라 이동한다. 최단 경로가 여러 개면 세금 합이 가장 적은 경로를 택한다. 가능한 목적지마다 JB가 내야 하는 세금의 최솟값을 구하라.

입력은 테스트 케이스 하나로만 주어진다.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 주어진다($2 \leq n\leq 50$, $n-1\leq m \leq \frac{n(n-1)}{2}$).

둘째 줄에는 회사별 기본 세금 $w_1,w_2,\dots,w_m$이 주어진다($1\leq w_i\leq 10\,000$).

이어서 $m$개의 줄이 주어진다. $i$번째 줄에는 정수 $u_i$, $v_i$, $c_i$가 주어지며($1\leq u_i,v_i\leq n$, $u_i\neq v_i$, $1\leq c_i\leq m$), 이는 $u_i$번 도시와 $v_i$번 도시를 잇는 양방향 도로이고 $c_i$번 회사가 관리한다는 뜻이다.

두 도시를 잇는 도로는 최대 하나이며, JB는 다른 모든 도시에 항상 도달할 수 있다.

$n-1$개의 줄을 출력한다. $k$번째 줄($1\leq k\leq n-1$)에는 목적지가 $k+1$번 도시일 때 JB가 내야 하는 세금의 최솟값을 한 정수로 출력한다.