Problem
Para a próxima Escola de Verão de Informática, decidiu-se preparar círculos tanto para os alunos como para todos os professores.
Por hábito de fazer coisas importantes no último momento, a designer finalizou o layout dois dias antes do início das aulas. Levará mais um dia para o fabricante fazer canecas e colocar uma imagem nelas. Leva apenas 24 horas para a OTAN levar as canecas da fábrica para a LKSH.
Um pedido de 10.000.000 canecas (ou seja, quantas as organizadoras pediram), é claro, não pode ser retirado em um voo. No entanto, para o primeiro voo, quero trazer o número máximo de canecas. Um caminhão pesado foi encomendado para o transporte. Mas há uma ressalva: em algumas estradas há um limite para o peso do carro. Portanto, se o carro estiver carregado de canecas até os olhos, talvez não seja possível usar o caminho mais curto, mas você terá que fazer um desvio. Pode até acontecer que, por causa disso, o caminhão não tenha tempo de chegar ao acampamento a tempo, e isso não pode ser permitido. Então, quantas canecas podem ser carregadas no carro para ter tempo de trazer essa carga valiosa a tempo e sem violar as regras de trânsito?
Entrada
A primeira linha contém os números n (1≤n≤500) e m - o número de nós no mapa rodoviário e o número de estradas, respectivamente. As próximas m linhas contêm informações sobre as estradas. Cada estrada é descrita em uma linha separada, como segue. Primeiro, são dados os números dos pontos de junção que são conectados por essa estrada, depois o tempo que leva para percorrer essa estrada e, finalmente, o peso máximo de um carro que pode circular nessa estrada. Sabe-se que todas as estradas conectam pontos diferentes, e para cada par de pontos existe no máximo uma estrada ligando-os diretamente. Todos os números são separados por um ou mais espaços.
Os pontos nodais são numerados de 1 a n. Ao mesmo tempo, a fábrica de canecas tem o número 1 e a LKSH - número n. O tempo de viagem na estrada é dado em minutos e não excede 1440 (24 horas). O limite de massa é dado em gramas e não excede um bilhão. Além disso, sabe-se que uma caneca pesa 100 gramas e um caminhão vazio - 3 toneladas.
Saída
Imprima um único número - o número máximo de canecas que podem ser trazidas no primeiro voo, não gastando mais de 24 horas.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |