시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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.

입력

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (2 ≤ n ≤ 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 ai, bi, di (1 ≤ ai, bin, aibi, 1 ≤ di ≤ 100 000) oznaczające, że skrzyżowania ai oraz bi są połączone dwukierunkową ulicą, którą należy odśnieżyć co najmniej di razy w ciągu dnia.

출력

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

예제 입력 1

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

예제 출력 1

8

힌트

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