== 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 ș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.
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 pentru fiecare sens sau pentru ambele sensuri. Pot exista mai multe autobuzuri care circulă între orașele _v_ și _w_
h2. Date de intrare
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ă).
Fișierul de intrare $traveling.in$ ...
h2. Date de ieșire
Î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$.
În fișierul de ieșire $traveling.out$ ...
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 |
| 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
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="traveling") ==
