== 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.
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 autobuze care circulă între orașele _v_ și _w_. Autobuzele care circulă între orașele_v_ și _w_ pot circula la ore diferite și prețul poate să difere.
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.
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 călătorie, programul va afisa varianta în care timpul petrecut pe drum este minim.
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$ 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_ si _e_ (acestea sunt pentru o variantă de călătorie).
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$
* _S_≤ 2000
* _N_≤ 3000 ...$
h2. Exemplu
