Tráfego

Você foi recentemente contratado por uma empresa de transportes, chamada Somente Bom Carros (S.B.C.). Sua primeira tarefa é aprender a rota utilizada para sair de uma filial até outra. Quando você estava analisando a rota, ficou claro que quem a determinou levou em conta apenas a distância, mas não a configuração dos semáforos de trânsito. Exiba as suas habilidades em programação encontrando a rota de menor tempo, levando em conta os semáforos.

Sua cidade contém $N$ esquinas e $M$ ruas unidirecionais. Cada uma das ruas possui um semáforo próximo a sua extremidade de destino, que funciona da seguinte forma:

No instante zero (que coincide com o horário que o veículo sairá da filial), o semáforo estará verde, e continuará assim por $G_i$ segundos, onde $i$ é o índice da rua.
No instante $G_i$ , o semáforo muda para vermelho, permanecendo assim por $R$ segundos.
No instante $G+R$ , o semáforo volta a ficar verde, e o processo continua assim indefinidamente.

Observe que não há nenhuma garantia de que em uma dada esquina no máximo um sinal ficará verde ao mesmo tempo. Curiosamente, a empresa W.M.P S/A (Wow, Much Problem. Such Accepted), considerou que o risco de colisão era excessivamente pequeno (algo relacionado ao baixo mdc dos períodos dos semáforos na cidade...)

Entrada

A primeira linha da entrada contém os inteiros $N$ e $M$ . Cada uma das $M$ linhas seguintes contém os inteiros $A_i, B_i, D_i, G_i, R_i$ , indicando uma rua indo da esquina $A_i$ até a $B_i$ , com distância $D_i$ , e cujo semáforo permanece no verde por $i$ segundos e no vermelho por $R_i$ .

A filial de origem é sempre a de numeração $1$ , enquanto a destino é sempre a de valor $N$ . É possível que existam duas ruas ligando o mesmo par de esquinas, em qualquer sentido (Serão consideradas ruas diferentes com semáforos indepedendentes). Assuma que o veículo se desloca uma unidade de distância por segundo.