== include(page="template/taskheader" task_id="traveling") ==
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 si 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_ variante de forma : autobuzul de la orașul _v_ la orașul _w_ (de asemenea și de la orașul _w_ la orașul _v_), timp _t_ ore, tarif _e_ euro.
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") ==
