Intr-un califat in desertul
Sahara exista N asezari-orase
conectate prin drumuri astfel incat fiecare oras se poate ajunge in oricare
altul, iar traseul dintre ele (succesiunea de drumuri) este unic. Intre orase
se efectueaza transporturi prin intermediul caravanelor, iar in decurs de un
an intre orice pereche de orase au loc doua transporturi: unul dus, altul intors.
Singura conditie pentru transporturi este ca, caravanele sa parcurga o distanta
de fix K drumuri; astfel vor
exista perechi de orase (cele intre care distanta este diferita de K)
intre care o caravana sa nu poata calatori. Califul a hotarat sa introduca taxe
pe drumuri, astfel fiecare caravana care trece intre doua orase trebuie sa plateasca
taxa pentru accesul pe drumul respectiv. La finele anului califul doreste sa
stie care este suma colectata din taxe pentru toate drumurile.
Date de intrare
Fisierul de intrare caravane.in
contine pe prima linie numarul de orase N.
Urmeaza N-1 linii de forma x
y t, cu semnificatia ca intre orasele x
si y exista drum, iar t
este valoarea taxei pe drumul dintre x
si y.
Date de iesire
Fisierul de iesire caravane.out
va contine o singura linie pe care va fi scris un singur numar intreg reprezentand
valoarea in RON colectata in decurs de un an in intreg califatul.
Restrictii
1 < N < 100 000
0 < K < 32 Taxa pentru fiecare drum este un numar natural <=
100
Suma colectata este un intreg reprezentabil pe 8 octeti cu semn.
Exemple
caravane.in
caravane.out
Explicatie
5 2
4 2 11
5 4 3
3 2 5
2 1 4
108
Singurele caravane
sunt intre perechile de orase 1-3, 1-4, 2-5, 3-1, 3-4, 4-1, 4-3 si 5-2
cu taxele respectiv 9, 15, 14, 9, 16, 15, 16, 14. Suma totala colectata
este 108.
stud. Gheorghe
Stefan
A.S.E. Bucuresti, Facultatea de Cibernetica stefangh@gmail.com