Preâmbulo

Pedrinho é um rapaz muito aventureiro, que nas férias viaja pelo mundo em busca de lugares afastados e com bonitas vistas.

Na sua viagem atual, Pedrinho está andando por uma escura floresta quando se depara com um perigoso desfiladeiro. Do outro lado do desfiladeiro ele sabe que existe um acampamento onde poderá descansar durante a noite para continuar suas aventuras no dia seguinte.

Para chegar até o acampamento, ele terá que utilizar pontes que estão suspensas sobre o desfiladeiro. As pontes foram construídas interligando altos pilares cravados no fundo do desfiladeiro.

O piso das pontes é feita de tábuas de tamanhos iguais. Mas as pontes são velhas, e algumas tábuas caíram. Felizmente, todas as tábuas que sobraram estão em perfeitas condições, ou seja, não existe o perigo de Pedrinho pisar em uma delas e a tábua cair. Além disso, em nenhuma das pontes duas tábuas consecutivas caíram, de forma que os buracos deixados pelas tábuas que caíram podem ser pulados com segurança.

No local onde Pedrinho se encontra existe uma placa mostrando as ligações entre as pontes e também quantas tábuas estão faltando em cada uma das pontes. Pedrinho está cansado e não há muita visibilidade durante a noite. Ele precisa, portanto, tomar muito cuidado para não cair em algum dos buracos.

Pedrinho possui um laptop na mochila, mas só o usa para comunicar-se com os amigos. Ele liga sua internet via satélite, encontra você on-line, e pede sua ajuda.

Tarefa

Sua tarefa é escrever um programa que receba as informações sobre as pontes (as ligações entre elas e a quantidade de tábuas faltando em cada uma) e calcule qual é o menor número de buracos que Pedrinho precisa pular para chegar ao outro lado do desfiladeiro.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada contém dois número inteiros N e M ($1 \leq N \leq 1000, 2 \leq M \leq 10000$) representando o número de pilares no desfiladeiro e o número de pontes, respectivamente. Cada uma das M linhas seguintes contém $3$ inteiros S, T, B ($0 \leq S \leq N + 1, 0 \leq T \leq N + 1 e 0 \leq B \leq 1000$), indicando que existe uma ponte ligando os pilares S e T , e que possui B buracos. Não existe linha representando ponte com S = T . O valor de pilar $0$ representa a borda do desfiladeiro onde Pedrinho está, e o valor de pilar $N + 1$ representa a borda do desfiladeiro onde está o acampamento. Não existem duas pontes distintas ligando o mesmo par de locais (pilares ou bordas do desfiladeiro).

Você pode supor que sempre existirá um caminho de pontes entre o lado do desfiladeiro em que Pedrinho se encontra até o lado do desfiladeiro onde está o acampamento.

Saída

Seu programa deve imprimir, na saída padrão, um número inteiro representando a menor quantidade de buracos que Pedrinho terá que pular para conseguir chegar ao acampamento.

Exemplos

Exemplo de entrada

2 5
0 1 1
0 2 3
0 3 9
1 3 2
2 3 2

Saída para o exemplo acima

3

Exemplo de entrada

4 9
0 1 1
0 3 4
0 4 2
1 2 5
1 5 3
2 5 5
3 4 2
3 5 5
4 5 8

Saída para o exemplo acima

4

Exemplo de entrada

21 40
1 0 601
2 1 54
3 1 144
4 2 786
5 1 548
6 2 446
7 3 649
8 0 726
9 5 588
10 8 749
11 5 48
12 4 214
13 7 547
14 12 508
15 7 118
16 14 201
17 12 586
18 0 470
19 9 815
20 9 475
21 7 448
22 4 897
22 14 882
22 13 31
17 4 354
2 11 845
20 14 796
6 9 184
8 22 957
20 17 661
19 13 788
13 14 473
2 7 817
4 1 258
8 16 682
22 20 657
12 1 45
20 6 965
15 21 116
3 16 842

Saída para o exemplo acima

1658