Problem
Para la próxima Escuela de Informática de Verano, se decidió preparar círculos tanto para escolares como para todos los profesores.
Con la costumbre de hacer cosas importantes en el último momento, el diseñador terminó el diseño dos días antes de que comenzaran las clases. El fabricante tardará otro día en hacer tazas y ponerles una imagen. La OTAN solo tarda 24 horas en llevar las tazas de la fábrica a LKSH.
Un pedido de 10 000 000 tazas (es decir, esa es la cantidad que pidieron los organizadores), por supuesto, no se puede retirar en un vuelo. Sin embargo, para el primer vuelo quiero traer el máximo número de tazas. Se ordenó un camión pesado para el transporte. Pero hay una advertencia: en algunas carreteras hay un límite en el peso del automóvil. Por lo tanto, si el automóvil está lleno de tazas hasta los ojos, es posible que no pueda usar la ruta más corta, pero tendrá que tomar un desvío. Incluso puede suceder que debido a esto, el camión no tenga tiempo de llegar al campamento a tiempo, y esto no se puede permitir. Entonces, ¿cuántas tazas se pueden cargar en el automóvil para tener tiempo de llevar esta valiosa carga a tiempo y sin violar las reglas de tránsito?
Entrada
La primera línea contiene los números n (1≤n≤500) y m - el número de nodos en el mapa de carreteras y el número de carreteras, respectivamente. Las siguientes m líneas contienen información sobre las carreteras. Cada camino se describe en una línea separada de la siguiente manera. En primer lugar, se dan los números de los puntos de cruce que están conectados por esta carretera, luego el tiempo que se tarda en viajar por esta carretera y, por último, el peso máximo de un coche que puede circular por esta carretera. Se sabe que todos los caminos conectan diferentes puntos, y para cada par de puntos hay como máximo un camino que los conecta directamente. Todos los números están separados por uno o más espacios.
Los puntos nodales se numeran del 1 al n. Al mismo tiempo, la planta para la producción de tazas tiene el número 1 y LKSH, el número n. El tiempo de viaje en la carretera se da en minutos y no excede 1440 (24 horas). El límite de masa se da en gramos y no supera los mil millones. Además, se sabe que una taza pesa 100 gramos y un camión vacío - 3 toneladas.
Salida
Imprima un solo número: el número máximo de tazas que se pueden llevar en el primer vuelo, en no más de 24 horas.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |