Tietoverkko

• Language:
  enfi
• Time limit: 1.00 s
• Memory limit: 512 MB

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$