Se da un arbore cu n noduri, ale carui muchii au costuri pozitive. Determinati diametrul ponderat: costul total al celui mai 'lung' (din punct de vedere al costului) drum dintre doua noduri.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n-1 linii, fiecare cu trei numere x y c, reprezentand o muchie intre x si y cu costul c.
- Date de iesire
- Se afiseaza diametrul ponderat al arborelui.
- Restrictii
- 1 <= n <= 100000, 1 <= c <= 10^6
Exemple
Exemplul 1
Intrare
5 1 2 3 1 3 5 2 4 2 2 5 4
Iesire
12
Exemplul 2
Intrare
1
Iesire
0