Nosaukums
Sniega tīrītājs (tiritajs)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
78%

Definīcija

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!


Ievaddatu raksturojums

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


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada naturāls skaitlis - mazākais nobraukto kilometru skaits.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā


Paraugdati

Stdin
5 2
1 2 1
2 3 2
3 4 2
4 5 1
Stdout
7

Stdin
5 1
1 2 1
2 3 1
3 5 1
3 4 1
Stdout
5

Stdin
4 1
1 3 2
1 2 3
1 4 4
Stdout
14

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.