Nosaukums
Maksas ceļi (samaksa)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

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 raksturojums

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 raksturojums

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.


Piezīmes

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


Paraugdati

Stdin
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
Stdout
11

Stdin
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
Stdout
-1

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.