Fișierul intrare/ieșire	traveling.in, traveling.out	Sursă	Shumen 2016 Juniori
Autor		Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	2.5 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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 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 călătorie, programul va afisa varianta în care timpul petrecut pe drum este minim.

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 si e (acestea sunt pentru o variantă de călătorie).

Date de ieșire

În fișierul de ieșire traveling.out afișează pe o singură linie 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.

Restricții

• S ≤ 2000
• N ≤ 3000
• M ≤ 5000
• 1 ≤ v ≤ N
• 1 ≤ w ≤ N
• 1 ≤ t ≤ 100
• 1 ≤ e ≤ 100

Exemplu

Explicație

...