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 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 .
h2. Date de intrare

Fișierul de intrare traveling.in ...

Date de ieșire

În fișierul de ieșire traveling.out ...

Restricții

• ... ≤ ... ≤ ...

Exemplu

Explicație

...