samaksa Maksas ceļi 1 sek.  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 Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 1998.gadā. Drukāšanai