Reţeaua de căi ferate din România este constituită din mai multe tronsoane, plasate astfel încât între oricare două oraşe există o singură rută de legătură. Fiecare tronson uneşte două oraşe distincte. O rută este constituită dintr-o succesiune de oraşe cu proprietatea că între oricare două oraşe consecutive există tronson de legătură. Lungimea unei rute este egală cu suma lungimilor tronsoanelor parcurse de-a lungul rutei.
CFR doreşte să modernizeze reţeaua de căi ferate pentru a introduce trenuri de mare viteză. Modernizarea se va realiza în următoarele condiţii:

1. toate tronsoanele aflate pe ruta unui tren de mare viteză trebuie să fie modernizate;
2. prin fiecare oraş va trece cel mult un tren de mare viteză;
3. suma lungimilor rutelor trenurilor de mare viteză este maximă.

Cerinţă

Scrieţi un program care să determine suma lungimilor rutelor trenurilor de mare viteză (maximă posibil).

Date de intrare

Fişierul de intrare tgv.in conţine pe prima linie un număr natural N, reprezentând numărul de oraşe. Oraşele sunt numerotate de la 1 la N. Fiecare dintre următoarele N-1 linii conţine descrierea unui tronson de cale ferată sub forma a trei numere naturale separate prin câte un spaţiu A B C cu semnificaţia “între oraşele A şi B există un tronson de lungime C”.

Date de ieşire

Fişierul de ieşire tgv.out va conţine o singură linie pe care va fi scrisă suma lungimilor rutelor trenurilor de mare viteză (maximă posibil).

Restricţii

• 1 ≤ N ≤ 2000
• 1 ≤ Lungimea unui tronson ≤ 1000000

Exemple

tgv.in	tgv.out	Explicatie
6 1 2 1 1 3 3 1 4 7 2 5 4 2 6 6	20	In primul exemplu vor fi modernizate 2 rute TGV: 3-1-4 (de lungime 3+7=10) şi 6-2-5 (de lungime 6+4=10). In total: 20.
tgv.in	tgv.out	Explicatie
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	11	În al doilea exemplu vor fi modernizate 2 rute TGV: 4-5-7-8-9 (de lungime 5+2+1+2=10) si ruta 1-2 (de lungime 1). În total 11.

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com