Cheap traveling#8565
Ivan the Speedy has to pay for the travel to the place of the next programming contest using his own personal funds. Moreover, he has only euros. For that reason, he carefully investigated the schedules of the public transportations and the prices, of course. Let us denote by Speedy's birthplace, by - the place where the contest will take place, and by 2, 3, \ldots, n-1 - the other villages he could travel through some of them. On the Internet, Ivan found possibilities in the form: the bus from village to village (as well as from to ) travels hours and costs Euro for each of both directions. There may be more than one bus traveling between to , and different buses traveling from to may travel for different times and at different ticket prices.
Write a program to find a trip from village to village at a cost, which is less than or equal to Euro. If there exists more than one such trip, the program must find a trip in which Speedy will spend minimal time sitting in the buses.
The first line contains the positive integers , and (s \le 2000, n \le 3000, m \le 5000). Each of the next lines contains integers - parameters , , and of one transportation possibility (1 \le v \le n, 1 \le w \le n, 1 \le t \le 100, 1 \le e \le 100).
Print the duration of the found trip. If there is no trip with a cost less than or equal to , print .
Example 1
Example 2