N pilsētas, kas apzīmētas ar naturāliem skaitļiem no 1 līdz N, savieno vienvirziena maksas ceļu sistēma. Katru ceļu raksturo ceļa garums un maksa (izteikta monētu skaitā), kas jāmaksā par šī ceļa lietošanu.

Ceļotājs vēlas nokļūt no pilsētas 1 līdz pilsētai N, bet viņam nav īpaši daudz monētu.

Atrodiet īsāko ceļu no pilsētas 1 līdz pilsētai N, par kuru ceļotājs varētu samaksāt!

Ievaddatu pirmā rinda satur naturālu skaitli K(1<=K<=10000) - ceļotājam piederošo monētu skaitu.
Faila otrajā rindā dots viens naturāls skaitlis - pilsētu skaits N (2<=N<=100).
Faila trešajā rindā dots viens naturāls skaitlis - ceļu kopskaits R (1<=R<=10000).
Katra no nākošajām R faila rindām apraksta vienu ceļu, uzdodot veselu skaitļu vērtības S,D,L un T. Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols.

• S ir pilsēta, kurā ceļš sākas, 1<=S<=N,
• D ir pilsēta, kurā ceļš beidzas, 1<=D<=N,
• L ir ceļa garums, 1<=L<=100,
• T ir maksa monētās par ceļa lietošanu, 0<=T<=100.

Ievērojiet ka divas pilsētas savā starpā var būt saistītas ar vairāk kā vienu ceļu.

Izvaddatu vienīgajā rindā jāizvada viens vesels skaitlis - īsākais ceļš no pilsētas 1 līdz pilsētai N, maksa par kuru nepārsniedz esošo monētu skaitu.
Ja šāds ceļš neeksistē, failā jāizvada skaitlis -1.

Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 1998.gadā.