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 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.

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ă).

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.

Restricții

• S ≤ 2 000
• N ≤ 3 000
• M ≤ 5 000
• 1 ≤ v ≤ N
• 1 ≤ w ≤ N
• 1 ≤ t ≤ 100
• 1 ≤ e ≤ 100

Exemplu