nagibni

Željeznicka mreža u jednoj zemlji sastoji se od odredenog broja pojedinacnih pruga. Svaka od njih
povezuje neka dva grada, poznata nam je duljina svake pruge, a izmedu svaka dva grada postoji
jedinstveni put željeznicom.<br><br>
Nedavno je vlada odlucila da se stari i spori vlakovi prodaju siromašnim zemljama, a da se od ludih
Japanaca kupe najmoderniji i najbrži nagibni vlakovi.<br><br>
Linija na kojoj vozi neki nagibni vlak se sastoji od niza gradova (barem dva) tako da izmedu svaka dva
susjedna grada na liniji postoji pruga, a duljinu linije definiramo kao zbroj duljina svih pruga na toj
liniji. Dvije linije ne smiju prolaziti kroz isti grad jer su vlakovi vrlo brzi pa postoji velika opasnost od
sudara.<br><br>

Napišite program koji ce odrediti neki raspored linija nagibnih vlakova, takav da kroz svaki grad prolazi
tocno jedna linija, a da zbroj duljina svih linija bude što je mogu ce veci.<br><br>

ulazi podaci<br>
U prvom retku se nalazi prirodni broj N, 1 < N <= 2000 (dvije tisu ce), broj gradova. Gradovi su
oznaceni brojevima od 1 do N.<br><br>
U sljedecih N-1 redaka se nalaze podaci o prugama. U svakom od tih redaka se nalaze tri prirodna broja
A, B i C - to znaci da izmedu grada A i grada B postoji pruga duljine C, 1 <= C <= 1000000 (milijun).<br><br>
Napomena: test podaci ce biti takvi da ce rješenje uvijek postojati.<br><br>
izlazni podaci<br>
U prvi i jedini redak treba ispisati traženi maksimalni zbroj iz teksta zadatka.<br><br>
test primjeri<br><br>
ulaz<br>
5<br>
1 2 10<br>
1 3 10<br>
1 4 10<br>
4 5 1<br><br>
izlaz <br>
21<br><br>

ulaz<br>
6<br>
1 2 1<br>
1 3 3<br>
1 4 7<br>
2 5 4<br>
2 6 6<br><br>
izlaz <br>
20<br><br>

ulaz<br>
9<br>
1 2 1<br>
2 4 2<br>
3 4 1<br>
4 5 5<br>
6 5 1<br>
5 7 2<br>
7 8 1<br>
8 9 2<br><br>
izlaz <br>11