Zapada a luat din nou prin surprindere primaria. Primarul a chemat de urgenta serviciul deszapeziri si a dat o lista cu strazile din oras care trebuie sa fie obligatoriu curatate. Primarul a selectat strazile din lista astfel incat numarul lor sa fie cat mai mic posibil, dar totusi intre oricare doua intersectii din oras sa existe legatura.
La serviciul deszapeziri lucreaza doi angajati, Vasilica si Ionica, pe doua utilaje. In acest moment si angajatii si utilajele se gasesc la sediul serviciului deszapezri, situat in una dintre intersectiile din oras. Un utilaj de deszapezire consuma 1 litru de benzina/1 metru (indiferent daca se deplaseaza pe o strada inzapezita sau deszapezita).
Vasilica si Ionica trebuie sa deszapezeasca toate strazile din lista data de primar, astfel incat cantitatea totala de benzina consumata sa fie minima.
Cand toate strazile din lista data de primar sunt curatate, utilajele pot fi parcate in ultima intersectie vizitata. Evident Ionica si Vasilica nu trebuie sa-si parcheze utilajele neaparat in aceeasi intersectie.

Cerinta

Scrieti un program care sa determine conatitatea minima de benzina necesara pentru curatarea tuturor strazilor din lista data de primar.

Date de intrare

Fisierul de intrare zapezi.in contine:
- pe prima linie doua numere naturale N si S, unde N este numarul de intersectii din oras, iar S este numarul de ordine al intersectiei in care se afla sediul serviciului deszapeziri, cea din care pleaca initial Vasilica si Ionica (intersectiile sunt numerotate de la 1 la N).
- fiecare dintre urmatoarele N-1 linii contine 3 numere naturale A B C cu semnificatia "intersectiile A si B sunt conectate direct printr-o strada de lungime C metri".

Date de iesire

Fisierul de iesire zapezi.out contine pe prima linie cantitatea minima de benzina necesara pentru curatarea tuturor strazilor din lista data de primar.

Restrictii

• 1 <= N <= 2000
• 1 <= S, A, B <= N
• 1 <= C <= 100

Exemple

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi