Pilsētas ielu tīkls sastāv no N krustojumiem un ielām, kas šos krustojumus savieno. Krustojumi ir numurēti ar naturāliem skaitļiem no 1 līdz N pēc kārtas.
Ziemā noteiktas pilsētas ielas tiek tīrītas tā, ka tīrāmo ielu skaits ir mazākais iespējamais, bet joprojām no jebkura krustojuma var nokļūt līdz jebkuram citam braucot pa ielām un tas ir izdarāms vienā vienīgā veidā. Pilsētai pieder divi sniega tīrītāji, kuri dienas sākumā atrodas noteiktā krustojumā.
Katras ielas garums ir izsakāms veselā skaitā kilometru un pilsētas varas iestādes ir ieinteresētas, lai visas nepieciešamās ielas būtu notīrītas un lai kopējais abu tīrītāju nobraukto kilometru skaits (ieskaitot atkārtotos pārbraucienus pa jau notīrītajām ielām) būtu pēc iespējas mazāks. Kad visas ielas ir notīrītas, sniega tīrītāji paliek pēdējā krustojumā. Personīgu iemeslu dēļ sniega tīrītāju vadītāji nevēlas darbu beigt vienā un tajā pašā krustojumā.
Uzrakstiet programmu, kas nosaka, kāds mazākais attālums sniega tīrītājiem jāveic, lai visas nepieciešamās ielas būtu notīrītas!
Teksta faila tiritaji.dat pirmajā rindā dotas divu naturālu skaitļu N(krustojumu skaits, 1 ≤N≤100000) un S(tā krustojuma numurs, kurā dienas sākumā atrodas sniega tīrītāji, 1 ≤S≤N) vērtības, kas atdalītas ar tukšumsimbolu.
Katrā no nākošajām N-1 faila rindām dots vienas tīrāmās ielas apraksts kā trīs naturālu skaitļu A,B un C vērtības, ko atdala tukšumsimboli. A un B ir to krustojumu numuri, kurus savieno dotā iela, bet C ir ielas garums kilometros (1≤C≤1000).
Teksta faila tiritaji.rez vienīgajā rindā jāizvada naturāls skaitlis - mazākais nobraukto kilometru skaits.
| tiritaji.dat | tiritaji.rez |
5 2 1 2 1 2 3 2 3 4 2 4 5 1 |
6 |
| tiritaji.dat | tiritaji.rez |
5 1 1 2 1 2 3 1 3 5 1 3 4 1 |
5 |
| tiritaji.dat | tiritaji.rez |
4 1 1 3 2 1 2 3 1 4 4 |
11 |