Laiko ribojimas: 5s

Atminties ribojimas: 256MB

Jei norite pateikti savo sprendimą - prisijunkite.

MST su metropoliu

Turime nekryptinį, svorinį, jungų grafą. Minimaliu dengiančiu medžiu su metropolio viršūne i vadinsime minimalų dengiantįjį medį, kuriam priklauso kiekviena briauna, einanti per viršūnę i. Tegu tokio medžio briaunų svorių suma yra S_i. Reikia apskaičiuoti S_i kiekvienai viršūnei i.

Pradiniai duomenys

Pirmoje eilutėje pateikiami skaičiai n ir m (1\\leqn\\leq10^5,1\\leqm\\leq3\\times10^5) - medžio viršūnių bei briaunų skaičiai.

Tolesnėse m eilučių pateikiama po tris skaičius - a, b ir w (1\\leqa,b\\leqn,1\\leqw\\leq10^9) - jie reiškia, kad tarp viršūnių a ir b yra svorio w briauna.

Garantuoja, kad jokia briauna nejungia viršūnės su ja pačia, ir tarp bet kurių dviejų viršūnių yra ne daugiau nei viena briauna.

Rezultatai

Išspausdinkite n eilučių. i-ojoje eilutėje turi būti vienintelis skaičius S_i - minimalaus dengiančiojo medžio su metropolio viršūne i svoris.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4 4
1 2 1
2 3 2
3 4 3
1 4 4
 
7
6
6
8