Šeštadieninė informatikos olimpiadininkų mokykla

Š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 () kaina yra . 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.) , o kai kuriais keliais antrą kartą važiuoti negalima, nes grėstų kalėjimas.

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

Pradiniai duomenys

Pirmoje eilutėje yra sveikieji skaičiai N () ir M (). Kiekviena iš tolesnių M eilučių apibūdina vieną kelią. Kelio apibūdinimą sudaro keturi sveikieji skaičiai: kelio jungiamų miestų numeriai, () ir (), kur reiškia, kad šiuo keliu antrą kartą važiuoti negalima.

Rezultatai

Vienintelėje eilutėje parašykite vieną skaičių, kelionės kainą. Jei dėl bet kokių priežasčių kelionė yra neįmanoma, rašykite 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