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 ≤ I ≤ M) 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

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