- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
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:
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$
- $1 \le n \le 5000$
- $1 \le x \le 10^9$
- $1 \le n \le 2 \cdot 10^5$
- $1 \le x \le 10^9$