- 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$
A computer network has $n$ computers and $n-1$ connections between two computers. Information may be exchanged between every pair of computers using the connections.
Each connection has a certain transfer speed, and the transfer speed between computers $a$ and $b$, $d(a,b)$, is defined as the speed of the slowest connection on the route between $a$ and $b$. Your task is to compute the sum of transfer speeds between all pairs of computers.
For example, consider the following computer network:
Input
The first line of input contains the integer $n$: the number of computers. The computers are numbered $1,2,\dots,n$.
After this, there are $n-1$ lines, which describe the connections. Each line has three integers $a$, $b$ and $x$: there is a connection between computers $a$ and $b$ with transfer speed $x$.
Output
Print one integer: the answer to the task.
Example
Input:
4
1 2 5
2 3 1
2 4 2
Output:
12
Subtask 1 (10 points)
- $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$