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 viens sniega tīrītājs, kurš 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 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ājs paliek pēdējā krustojumā.
Uzrakstiet programmu, kas nosaka, kāds mazākais attālums sniega tīrītājam jāveic, lai visas nepieciešamās ielas būtu notīrītas!
Teksta faila tiritajs.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ājs, 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 tiritajs.rez vienīgajā rindā jāizvada naturāls skaitlis - mazākais nobraukto kilometru skaits.
| tiritajs.dat | tiritajs.rez |
5 2 1 2 1 2 3 2 3 4 2 4 5 1 |
7 |
| tiritajs.dat | tiritajs.rez |
5 1 1 2 1 2 3 1 3 5 1 3 4 1 |
5 |
| tiritajs.dat | tiritajs.rez |
4 1 1 3 2 1 2 3 1 4 4 |
14 |