Aborigines from the planet Sheshiner are very fond of terrestrial pineapples. After visiting them, Alice decided to send a few of them as a gift. There are only 24 hours to deliver fresh pineapples.
Alice wants to send as many pineapples as possible. Captain Poloskov decided to help her and happily agreed to fly on his spaceship. But there is one caveat: on some space routes, you can refuel a ship that does not exceed the maximum weight. And you always need to refuel the ship on the way, otherwise it simply will not fly. Therefore, if the ship is filled with pineapples to the maximum, then it will not be possible to refuel it on the way and therefore it will not be possible to use the shortest routes, and you will have to fly through other planets. It may even happen that the ship does not have time to reach Sheshinyera in time, and the pineapples will go bad.
So, how many pineapples can be loaded into a spaceship to deliver the cargo on time?
Input
The program receives several lines as input. The first line contains the numbers
n (1 <= n <= 500) and
m - the number of planets and the number of space routes between planets, respectively. The following
m lines contain information about the routes. Each route is described on a separate line as follows. First, the numbers of the planets that are connected by a space route are indicated, then the time spent on a flight along this route, and, finally, the maximum spacecraft that can be refueled along this route. It is known that all space routes connect different planets, and for each pair of planets there is at most one route directly connecting them. All numbers are separated by one or more spaces.
Planets are numbered from
1 to
n. Planet Earth has number 1, and Sheshiner's planet has number
n. The flight time along the route is specified in minutes and does not exceed 1440 (24 hours). The mass limit is given in grams and does not exceed one billion. In addition, it is known that one pineapple weighs 100 grams, and an empty ship weighs 3 tons.
Imprint
Print a single number - the maximum number of pineapples that can be delivered within 24 hours.
Examples
| # |
Input |
Output |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2
|