Transportation
Yandex has decided to gift original mugs to all students and teachers at LCSH. However, the number of mugs required is so large that the manufacturer delivered them to the Yandex office at the last minute. With only 24 hours remaining to transport the mugs from Moscow to "Berendeyevy Polyany," the challenge is to determine how many mugs can be loaded onto a truck for the first trip.
The order consists of 10^7 mugs, which cannot be delivered in a single trip. For the initial trip, the goal is to transport as many mugs as possible. A large truck has been arranged for this purpose, but there is a complication: some roads have weight restrictions for vehicles. If the truck is loaded to its full capacity, it might not be able to take the shortest route and may need to take a detour. In the worst-case scenario, the truck might not reach the camp on time, which is unacceptable.
The task is to determine the maximum number of mugs that can be loaded onto the truck so that the delivery is completed on time without breaking any traffic regulations.
Input
The first line contains the integers n (1 ≤ n ≤ 500) and m, representing the number of nodes in the road network and the number of roads, respectively. The next m lines provide details about each road. Each road is described by the numbers of the nodes it connects, the time required to travel it, and the maximum allowable vehicle weight. All roads connect different nodes, and there is at most one road directly connecting any pair of nodes. All numbers are separated by one or more spaces.
Nodes are numbered from 1 to n. The Yandex office is node 1, and "Berendeyevy Polyany" is node n. Travel time on each road is given in minutes and does not exceed 1440 (24 hours). The weight limit is specified in grams and does not exceed one billion. Each mug weighs 100 grams, and the empty truck weighs 3 tons.
Output
Output a single number: the maximum number of mugs that can be delivered on the first trip, ensuring the journey takes no more than 24 hours.