Tasks:
 
Task DescriptionDiscussion (0)
Task :: 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.

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.

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.

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.

ulazi podaci
U prvom retku se nalazi prirodni broj N, 1 < N <= 2000 (dvije tisu ce), broj gradova. Gradovi su oznaceni brojevima od 1 do N.

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).

Napomena: test podaci ce biti takvi da ce rješenje uvijek postojati.

izlazni podaci
U prvi i jedini redak treba ispisati traženi maksimalni zbroj iz teksta zadatka.

test primjeri

ulaz
5
1 2 10
1 3 10
1 4 10
4 5 1

izlaz
21

ulaz
6
1 2 1
1 3 3
1 4 7
2 5 4
2 6 6

izlaz
20

ulaz
9
1 2 1
2 4 2
3 4 1
4 5 5
6 5 1
5 7 2
7 8 1
8 9 2

izlaz
11
Submit Solution
:
:
Available Languages
Task info
Name:nagibni
Time:0.25 sec.
Memory:16 MB
#Tests:10
AddedBy: admin
Task Ratings
Difficulty:

3.4 (7 votes)
Quality:

2.7 (7 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
nikolas 0.007 s.
nemanja1990 0.008 s.
troka 0.009 s.
kfrane 0.009 s.
majce 0.01 s.
stjepang 0.011 s.
tgudlek 0.011 s.
The_Philosopher 0.011 s.
mirosl@v 0.012 s.
ip314 0.012 s.
Solved By