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.

Saída

A saída consiste em uma linha com um único inteiro, o tempo mínimo necessário para se deslocar até a outra filial. Caso seja impossível, imprima -1.

Restrições

• $$3 \leq N \leq 5\cdot 10^4$$
• $$1 \leq M \leq 5\cdot 10^5$$
• $$1 \leq A,B \leq N$$
• $$1 \leq D \leq 1000$$
• $$1 \leq R,G \leq 1000$$

Exemplos