보물 찾기

페리 해적은 일곱 바다를 누비고 있다! 그의 지도에는 $M$개의 바닷길로 이어진 $N$개의 섬이 있다. $i$번째 바닷길은 섬 $a_i$와 $b_i$를 잇고, 어느 방향으로 지나든 $c_i$ 코인이 든다. 바다 괴물을 물리치는 데도 돈이 꽤 든다. 페리는 $N$개의 섬을 모두 정찰했고, $i$번째 섬에 $v_i$ 코인이 든 보물 상자가 있다는 것을 알아냈다.

이제 항해 경로를 계획한다. 그는 섬 $x$에서 출발해 섬 $y$에서 끝나는 바닷길 경로를 따라 항해한다(빈 경로일 수도 있다). 항해가 끝나면 섬 $y$의 보물 상자를 열어 전리품을 챙긴다.

문제가 하나 있다. 페리는 자신이 지금 어느 섬에 있는지 모른다. 그래서 출발할 수 있는 섬 $x$마다, 섬 $x$에서 출발하는 모든 항해 중 얻을 수 있는 코인의 최댓값을 구하려 한다. 페리가 고른 경로는 어느 것이든 지나갈 수 있을 만큼 코인이 충분하다고 가정해도 된다. 그는 항해의 순이익만 신경 쓴다.

첫째 줄에 공백으로 구분된 두 정수 $N$과 $M$이 주어진다.

둘째 줄에는 공백으로 구분된 $N$개의 정수 $v_1, v_2, \ldots, v_N$($0 \le v_i \le 10^9$)이 주어진다.

이어지는 $M$개의 줄에는 각각 세 정수 $a_i$, $b_i$($1 \le a_i, b_i \le N$), $c_i$($0 \le c_i \le 10^9$)가 주어진다. 두 섬 사이의 바닷길은 최대 하나이며, 각 바닷길은 서로 다른 두 섬을 잇는다.

$N$개의 줄을 출력한다. $x$번째 줄에는 섬 $x$에서 출발하는 항해 중 얻을 수 있는 순이익(코인)의 최댓값을 출력한다.