W Bajtocji nastała zima. Bajtazar, kierowca pługu, nie dał się zaskoczyć i ruszył do odśnieżania ulic Bajtogrodu.

Sieć drogowa w Bajtogrodzie składa się z $ n $ skrzyżowań połączonych $n-1$ dwukierunkowymi ulicami. Z każdego skrzyżowania do każdego innego da się dojechać bez zawracania dokładnie jedną trasą złożoną z jednej lub większej liczby ulic.

Śnieg pada nieustannie, dlatego ulice należy ciągle odśnieżać od nowa. Dla każdej ulicy Bajtazar wie, ile co najmniej razy powinien ją odśnieżyć w ciągu dnia (nie jest dla niego istotne, w których momentach dnia to uczyni). Bajtazar może rozpocząć odśnieżanie przy dowolnym skrzyżowaniu. Chciałby on tak zaplanować swą pracę, by łączna liczba przejechanych ulic była jak najmniejsza. Oczywiście wielokrotne przejechanie tej samej ulicy należy liczyć wiele razy.

Input Format

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ n $ ($2 \le n \le 500\,000$) oznaczającą liczbę skrzyżowań w Bajtogrodzie. W kolejnych $ n $ - 1 wierszach opisane są poszczególne ulice. W każdym z tych wierszy znajdują się trzy liczby całkowite $ a_{i} $, $ b_{i} $, $ d_{i} $ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$, $1 \le d_i \le 100\,000$) oznaczające, że skrzyżowania $ a_{i} $ oraz $ b_{i} $ są połączone dwukierunkową ulicą, którą należy odśnieżyć co najmniej $ d_{i} $ razy w ciągu dnia.

Output Format

Na wyjście należy wypisać jeden wiersz zawierający minimalną liczbę ulic, którymi musi przejechać Bajtazar, by spełnić podane wymagania.

Example

Input

6
1 2 1
2 3 1
3 5 2
5 4 1
5 6 1

Output

8

Notes

Najlepsza trasa Bajtazara przebiega ośmioma ulicami: 1 → 2 → 3 → 5 → 4 → 5 → 6 → 5 → 3.