W Bajtocji jest n miast (2 <= n <= 1 000 000) ponumerowanych kolejnymi liczbami naturalnymi od 1 do n. Niektóre z miast są połączone dwukierunkowymi drogami. Władze Bajtocji bardzo oszczędzały na budowie dróg w państwie i choć z każdego miasta da się dotrzeć za pomocą dróg do każdego innego miasta, to można to zrobić tylko na jeden sposób nie będąc dwukrotnie w tym samym mieście.
W Bajtocji działa firma kurierska o nazwie Bajtocka Sieć Przesyłek, w skrócie BSP. BSP oferuje przesyłki kurierskie pomiędzy dowolnymi dwoma miastami w Bajtocji. Cennik BSP wygląda następująco:
Twoja firma chce z jednego z miast wysłać przesyłki do wszystkich innych miast. Zarząd Twojej firmy zastanawia się, ile to by kosztowało, zależnie od tego, z którego miasta przesyłki byłyby wysyłane. Napisz program, który pomoże zarządowi przewidzieć koszty wysyłek.
W pierwszym wierszu wejścia znajduje się liczba całkowita n (2 <= n <= 1 000 000) oznaczająca liczbę miast w Bajtocji. Kolejne n-1 wierszy zawiera opisy dróg w Bajtocji, po jednej w każdej linii. Każda droga reprezentowana jest przez trzy liczby całkowite a,b,c oddzielone pojedynczymi odstepami (1 <= a,b <= n, a =/= b, 1 <= c <= 1 000). Oznaczają one drogę dwukierunkową między miastami o numerach a i b o długości c kilometrów.
Twój program powinien wypisać dokładnie n liczb, po jednej w każdym wierszu. Liczba w i-tym wierszu powinna oznaczać sumaryczny koszty wysłania przesyłek z miasta o numerze i.
Dane:
10 1 2 3 2 3 5 3 4 1 4 5 7 4 9 11 9 10 2 5 6 1 5 7 4 5 8 10
dają odpowiedź:
141 117 87 83 97 105 129 177 149 165
[Zgłoś rozwiązanie] [Moje zgłoszenia]