Maksas ceļi

Uzdevums

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!

Ievaddati

Teksta faila samaksa.in 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.

Izvaddati

Teksta faila samaksa.out 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.

Piemērs

samaksa.in	samaksa.out
5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2	11
samaksa.in	samaksa.out
0 4 4 1 4 5 2 1 2 1 0 2 3 1 1 3 4 1 0	-1

Atsauces