Tietoverkko (Network)

• 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$
  

---

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:

We have $d(1,2)=5$, $d(1,3)=1$, $d(1,4)=2$, $d(2,3)=1$, $d(2,4)=2$ and $d(3,4)=1$, so the sum of transfer speeds is $12$.

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$
  

Subtask 2 (15 points)

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

Subtask 3 (75 points)

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