Problem
Pour la prochaine école d'informatique d'été, il a été décidé de préparer des cercles pour les écoliers et tous les enseignants.
Ayant l'habitude de faire les choses importantes au tout dernier moment, le designer a terminé la mise en page deux jours avant la rentrée. Il faudra encore un jour au fabricant pour fabriquer des tasses et y apposer une image. Il ne faut que 24 heures à l'OTAN pour transporter les tasses de l'usine à LKSH.
Une commande de 10 000 000 de tasses (à savoir, c'est le nombre commandé par les organisateurs), bien sûr, ne peut pas être emportée en un seul vol. Cependant, pour le premier vol, je veux apporter le maximum de tasses. Un camion lourd a été commandé pour le transport. Mais il y a une mise en garde : sur certaines routes, il y a une limite au poids de la voiture. Par conséquent, si la voiture est chargée de tasses jusqu'aux globes oculaires, il ne sera peut-être pas possible d'utiliser l'itinéraire le plus court, mais vous devrez faire un détour. Il peut même arriver qu'à cause de cela, le camion n'ait pas le temps d'atteindre le camp à temps, et cela ne peut être autorisé. Alors, combien de tasses peuvent être chargées dans la voiture afin d'avoir le temps d'apporter cette précieuse cargaison à temps, et sans enfreindre le code de la route ?
Entrée
La première ligne contient les nombres n (1≤n≤500) et m - le nombre de nœuds dans la feuille de route et le nombre de routes, respectivement. Les m lignes suivantes contiennent des informations sur les routes. Chaque route est décrite sur une ligne distincte comme suit. D'abord, les numéros des points de jonction qui sont reliés par cette route sont donnés, puis le temps qu'il faut pour parcourir cette route, et enfin, le poids maximum d'une voiture autorisée à rouler sur cette route. On sait que toutes les routes relient différents points, et pour chaque paire de points, il y a au plus une route les reliant directement. Tous les nombres sont séparés par un ou plusieurs espaces.
Les points nodaux sont numérotés de 1 à n. Dans le même temps, l'usine de production de tasses porte le numéro 1 et LKSH - numéro n. Le temps de trajet sur la route est donné en minutes et ne dépasse pas 1440 (24 heures). La limite de masse est donnée en grammes et ne dépasse pas un milliard. De plus, on sait qu'une tasse pèse 100 grammes et qu'un camion vide - 3 tonnes.
Sortie
Imprimez un seul chiffre - le nombre maximum de tasses pouvant être emportées lors du premier vol, sans passer plus de 24 heures.
Exemples
| # |
Entrée |
Sortie |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
2 |