Problem 138: regate

În tărâmul ONI se află N regate legate între ele prin M muchii bidirecționale. Se garantează că se poate ajunge de la orice regat la oricare alt regat folosind aceste muchii. Aceste regate vor să facă alianțe între ele și se vor folosi de puncte de frontieră pentru a realiza acest lucru.

Fiecare muchie i, unde 1 ≤ i ≤ M, are asociat un număr natural $c_i$ reprezentând costul construcției unui punct de frontieră pe aceasta. Mai mult decât atât, fiecare regat i, unde 1 ≤ i ≤ N, are asociat un număr natural $r_i$ reprezentând costul construcției unui punct de frontieră la intrarea acestuia.

Pentru ca regatul X să intre într-o alianță cu regatul Y, unde 1 ≤ X, Y ≤ N, X ≠ Y , acesta are două opțiuni:

construiește un punct de frontieră pe o singură muchie i cu cost $c_i$ , astfel încât orice drum de la X la Y trece prin acest punct de frontieră;
construiește un punct de frontieră la intrarea regatului său (regatului X) cu cost $r_X$ .

Evident, regatul X va alege costul minim pentru a intra într-o alianță cu regatul Y. Vom nota acest cost minim cu Cost(X, Y). Atenție, costul ca regatul X să intre într-o alianță cu regatul Y poate fi diferit de costul ca regatul Y să intre într-o alianță cu regatul X!

Pentru ca regatul X să fie într-o alianță perfectă acesta trebuie să facă alianță cu toate celalate regate.

Atenție, în formarea unei alianțe nu se iau în considerare punctele de frontieră construite în formarea altor alianțe. Cu alte cuvinte, Cost(X, Y) se calculează independent pentru fiecare pereche (X, Y)!

Cerință

Pentru fiecare regat trebuie să calculați costul pe care acesta trebuie să-l plătească pentru a fi într-o alianță perfectă. Cu alte cuvinte, pentru fiecare regat i, unde 1 ≤ i ≤ N, trebuie să calculați $\sum _{j=1,j \ne i} ^N \text{Cost}(i, j)$ .

Date de intrare

Pe prima linie a fișierului de intrare regate.in se află N și M, numărul de regate, respectiv, numărul de muchii bidirecționale. Pe a doua linie se găsesc numerele $r_1, ..., r_N$ , separate prin spații, unde $r_i$ reprezintă costul construcției unui punct de frontieră la intrarea regatului i. Pe următoarele M linii se află câte trei numere naturale $a_i, b_i, c_i$ , separate prin spații, 1 ≤ i ≤ M, semnificând că există o muchie bidirecțională între regatul $a_i$ și regatul $b_i$ , iar $c_i$ reprezintă costul construcției unui punct de frontieră pe muchia i.

Date de ieșire

În fișierul de ieșire regate.out se vor afișa N linii. Fiecare linie i va conține un singur număr întreg, reprezentând costul ce trebuie plătit pentru ca regatul i să fie într-o alianță perfectă, cu alte cuvinte, $\sum _{j=1,j \ne i} ^N \text{Cost}(i, j)$ .

Restricții și precizări

1 ≤ N ≤ 200 000
1 ≤ M ≤ 200 000
$1 ≤ ci ≤ 10^9$
$1 ≤ ri ≤ 10^9$
$1 ≤ a_i, b_i ≤ N, a_i \neq b_i$ (adică nu există muchie de la un regat la el însuși)
Între două regate poate exista cel mult o muchie

Subtask 1 (5 puncte)

N ≤ 2000 și M = N − 1, iar regatele și muchiile vor forma un lanț în ordinea 1, 2, ..., N

Subtask 2 (10 puncte)

N ≤ 200 și M ≤ 400

Subtask 3 (20 puncte)

N ≤ 2000 și M ≤ 2000

Subtask 4 (10 puncte)

Toate numerele din șirul c sunt egale

Subtask 5 (35 puncte)

M = N − 1

Subtask 6 (20 puncte)

Fără restricții suplimentare

Exemple

regate.in

5 5
8 13 9 7 12
1 2 10
2 3 10
3 4 10
4 5 10
1 3 10

regate.out

Explicație

De exemplu, pentru regatul 2 avem:
Cost(2, 1) = 13
Cost(2, 3) = 13
Cost(2, 4) = 10
Cost(2, 5) = 10

Suma acestora este 46.

Atenție că, de exemplu, în calculul lui Cost(2, 1), nu putem pune un punct de frontieră pe muchia (1, 2) de cost 10, deoarece există drumul 2 → 3 → 1 care nu trece prin muchia (1, 2).

regate