== include(page="template/taskheader" task_id="traveling") ==
Ivan Cel Rapid trebuie să plătească din fonduri proprii pentru călătoria spre locul unde urmează să se desfășoare următorul concurs de programare.
Ivan Cel Rapid trebuie să plătească din fonduri proprii călătoria spre locul unde urmează să se desfășoare următorul concurs de programare. El dispune doar de _S_ euro. Din acest motiv, el a verificat cu mare grijă programul mijloacelor de transport în comun și bineînțeles prețurile. O să notăm cu 1 locul de plecare, cu _N_ locul unde urmează să se desfașoare concursul și cu 2, 3, ... _N_ - 1 celelalte orașe prin care ar putea să treacă. Ivan a găsit _M_ curse de forma: cursa între orașele _v_ și _w_ durează _t_ ore și are tariful de _e_ Euro în ambele sensuri. Pot exista mai multe curse între orașele _v_ și _w_. Acestea pot varia atât ca durată cât și ca tarif.
Să se scrie un program care găsește o călătorie de la orașul 1 la orașul _N_ la un tarif mai mic sau egal cu [_S_]. Dacă există mai multe variante de a călători, programul va afisa varianta în care timpul petrecut pe drum este minim.
h2. Date de intrare
Fișierul de intrare $traveling.in$ ...
Fișierul de intrare $traveling.in$ conține pe prima linie numerele întregi pozitive [_S_], [_N_] și [_M_]. Fiecare din următoarele _M_ linii conține 4 numere întregi: [_v_], [_w_], [_t_] și [_e_] (descriind o cursă).
h2. Date de ieșire
În fișierul de ieșire $traveling.out$ ...
În fișierul de ieșire $traveling.out$ se va găsi durata călătoriei. Dacă nu se găsește nicio variantă de călătorie la un tarif mai mic sau egal cu [_S_], programul o să afișeze $-1$.
h2. Restricții
* $... ≤ ... ≤ ...$
* $_S_ ≤ 2 000$
* $_N_ ≤ 3 000$
* $_M_ ≤ 5 000$
* $1 ≤ _v_ ≤ _N_$
* $1 ≤ _w_ ≤ _N_$
* $1 ≤ _t_ ≤ 100$
* $1 ≤ _e_ ≤ 100$
h2. Exemplu
table(example).
|_. traveling.in |_. traveling.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 4 6
1 2 2 5
1 3 2 2
1 4 7 3
2 3 1 2
2 4 2 3
3 4 5 2
|5
|
|4 4 6
1 2 2 5
1 3 2 2
1 4 7 5
2 3 1 2
2 4 2 3
3 4 5 3
|-1
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="traveling") ==
