Baikeriai


Pradinių duomenų failas:
baikeriai.in  
Rezultatų failas:
baikeriai.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Šalyje yra N miestų. Miestus jungia M abipusių kelių. Tarp dviejų miestų gali būti bet koks kiekis kelių. Grupė baikerių iš miesto 1 ketina keliauti į baikerių susitikimą, organizuojamą mieste N, ir grįžti namo. Važiavimo keliu I (1 ≤ IM) kaina yra \(a_{I}\). Tačiau, dėl keliamo triukšmo, agresyvaus važiavimo bei pastovaus taisyklių laužymo, antrą kartą važiuojant tuo pačiu keliu atsiranda papildomų mokesčių (baudos, kyšiai ir t.t.) \(b_{I}\), o kai kuriais keliais antrą kartą važiuoti negalima, nes grėstų kalėjimas.

Raskite mažiausią tokios kelionės kainą.

Pradiniai uomenys

Pirmoje pradinių duomenų failo eilutėje yra skaičiai N (2 ≤ N ≤ 1000) ir M (1 ≤ M ≤ 10000). Kiekviena iš tolesnių M eilučių apibūdina vieną kelią.
Kelio apibūdinimą sudaro keturi sveiki skaičiai: kelio jungiamų miestų numeriai, \(a_{I}\) (0 ≤ \(a_{I}\) ≤ 100) ir
\(b_{I}\) (-1 ≤ \(b_{I}\) ≤ 100), kur \(b_{I}\) = -1 reiškia, kad šiuo keliu antrą kartą važiuoti negalima.

Rezultatai

Pirmoje rezultatų eilutėje programa turi įrašyti kelionės kainą. Jei dėl bet kokių priežasčių kelionė yra neįmanoma, reikia įrašyti 0.

Pavyzdžiai

Pradiniai duomenys Rezultatai
6 8
1 2 10 1
1 3 5 -1
2 3 10 10
3 4 10 10
4 5 10 10
2 5 2 0
5 6 10 1
4 6 5 -1
42
2 1
1 2 10 -1
0