Tietoverkossa on n tietokonetta ja n-1 kahden koneen välistä yhteyttä. Jokaisen koneparin välillä pystyy välittämään tietoa yhteyksien avulla.

Jokaisella yhteydellä on tietty siirtonopeus, ja koneiden a ja b välinen siirtonopeus d(a,b) on pienin siirtonopeus a:n ja b:n välisellä reitillä. Tehtäväsi on laskea summa siirtonopeuksista kaikkien koneparien välillä.

Tarkastellaan esimerkkinä seuraavaa tietoverkkoa:

Tässä tapauksessa d(1,2)=5, d(1,3)=1, d(1,4)=2, d(2,3)=1, d(2,4)=2 ja d(3,4)=1, joten nopeuksien summa on 12.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: tietokoneiden määrä. Tietokoneet on numeroitu 1,2,\dots,n.

Tämän jälkeen on n-1 riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kolme lukua a, b ja x: koneiden a ja b välissä on yhteys, jonka siirtonopeus on x.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus.

Esimerkki

Syöte:

4
1 2 5
2 3 1
2 4 2

Tuloste:

12

Osatehtävä 1 (10 pistettä)

• 1 \le n \le 100
• 1 \le x \le 100

Osatehtävä 2 (15 pistettä)

• 1 \le n \le 5000
• 1 \le x \le 10^9

Osatehtävä 3 (75 pistettä)

• 1 \le n \le 2 \cdot 10^5
• 1 \le x \le 10^9