It was decided to prepare specially designed cups with a competition logotype of Ural Championship 2005 for each participant and for any observer, who wish to have such a cup.

Having a habit to do such important things at the last moment, designer finished his job with a cup design two days before the Championship. So there is a shortage of time. One day is needed to manufacture the cups and to put Championship logotype onto them. So there are 24 hours left to deliver the cups from an enterprise to contest area.

Of course, it is impossible to deliver ten million cups (this is the amount of cups ordered by organizing committee) in a one trip. But it is desirable to deliver as many of cups as possible in a one trip.

Organizing committee ordered one big delivery truck. One would try to load the truck by the cups for it's full load. But some roads have weight limit: if the weight of the truck exceeds the road weight limit, it can not pass the road. So it is possible, that fully loaded truck can not go along the shortest route of delivery, it has to use longer route with acceptable weight limit. Moreover, it is possible, that the fully loaded truck will not deliver the cups in time. And it is definitely unacceptable.

So, how many cups can be loaded into the truck, so that this precious load could be delivered in time without violation of road weight limits?

The first line contains two numbers: the total number of road map nodes N (1 ≤ N ≤ 500) and the total number of roads M. Next M lines contain information about the roads. Each road is described on a separate line in the following way. Two numbers of road map nodes connected by the road go first. They are followed by the time required to pass the road. Finally the weight limit for the road goes. It is known that each road connects two different road map nodes. And for any two road map nodes there is at most one road connecting them. All numbers are separated with a one or more space(s).

Road map nodes are numbered with an integers in a range from 1 to N. Enterprise, where the cups are manufactured, is always placed in a node 1. And Urals Championship area always in at node N. Road passage time is given in minutes, and it does not exceed 1440 (24 hours). Weight limit is given in grammes, and it does not exceed 10⁹. One cup has a weight of 100 grammes, and the empty truck has a weight of 3 tonnes (1 tonne = 1000 kilogrammes; 1 kilogramme = 1000 grammes).

Print the only number: the total amount of the cups (it must be as much as possible), which can be delivered in the first trip of the truck in a time of 24 hours.