Caminho mais tranquilo

#6
Made by: Crazynds
500MB
1s

Jorge mora numa floresta, e quer chegar em casa o mais descansado possivel, para isso ele usa os riachos a seu favor para se locomover entre as regiões. Alguns riachos Jorge precisa remar contra a correnteza, então acaba gastando energia, e em outros ele pode ir a favor da correnteza e assim descançar, ganhando um pouco de energia no percurso.

Será dado o número da regiões, e também os riachos que ligam cada região. Alguns riachos são impossiveis nadar contra a correnteza, e outros Jorge não utiliza a favor da correnteza por ser muito turbulento, então nem todos os riachos é possivel usa-los como caminho para ida e volta, por isso cada caminho usável sera dado separadamente.

Ajude Jorge a chegar em casa o mais tranquilo possivel, e consequentemente, com o máximo de energia possivel.

Input

Será dado um $N$ representando o número de regiões e um $M$ representando o número de caminhos pelos rios $(1<=N<=10^4, <= M <= 2*10^4)$, e após serão dadas $M$ linhas representando informações de caminhos usando algum riacho. Jorge sempre sai da região 1 e a sua casa é na região $N$.

Cada caminho é composto por 3 números, $a$,$b$ e $c$ $(1<=a,b<=N, -10^6 <= c <= 10^6)$, o primeiro é a região da nascente do riacho, o segundo é onde a região no qual o riacho desagua. O terceiro número representa a energia que jorge gasta para pegar aquele caminho.

Output

Qual a menor quantidade de energia Jorge vai gastar para chegar até sua casa. Note que Jorge pode ganhar energia nesse caminho, então o resultado poderá ser negativo.

Sempre vai haver um caminho da origem de Jorge até a sua casa, e não vão existir casos com ciclos negativos.

Input Example
Output Example 
4 10
1 2 -8
1 3 5
1 4 6
2 3 8
2 4 10
3 1 2
3 2 -8
4 1 -1
4 2 2
4 3 -2
2

6 15
1 3 -1
1 5 9
2 1 2
2 5 1
2 6 -2
3 1 8
3 2 8
3 6 -8
4 1 5
4 3 -9
4 5 8
5 1 1
5 4 1
5 6 1
6 1 10

-9