Beaverland é formado por $N$ cidades, numeradas de $1$ a $N$. Há $M$ estradas ligando as cidades, numeradas de $1$ a $M$. A estrada $i$ ($1 \le i \le M$) liga as cidades $A_i$ e $B_i$ nos dois sentidos e tem comprimento $C_i$. É possível ir de qualquer cidade a qualquer outra passando por algumas estradas.
Bitaro é um castor que mora na cidade $1$ e estuda em uma escola na cidade $N$. Ele costuma fazer o mesmo percurso até a escola. Esse percurso satisfaz as seguintes condições.
- Seja $L$ a distância mínima entre a cidade $1$ e a cidade $N$.
- O percurso de Bitaro até a escola liga as cidades $1$ e $N$ e tem comprimento $L$.
Como hoje está um belo dia, Bitaro decidiu voltar para casa por um caminho mais longo, isto é, um percurso da cidade $N$ à cidade $1$ com comprimento maior que $L$. Como ele se entedia facilmente, não quer visitar a mesma cidade mais de uma vez. Portanto, ao voltar para casa por esse caminho, não é permitido visitar a mesma cidade mais de uma vez nem dar meia-volta durante o trajeto.
Dadas as informações sobre as cidades e estradas de Beaverland, escreva um programa que determine se existe um caminho mais longo da escola até a casa de Bitaro.
Entrada
Leia os seguintes dados da entrada padrão. Todos os valores são inteiros.
$$ \begin{array}{lll} N & M \\ A_1 & B_1 & C_1 \\ A_2 & B_2 & C_2 \\ \vdots \\ A_M & B_M & C_M \end{array} $$
Saída
Escreva uma linha na saída padrão. Escreva 1 se existir um percurso até a casa de Bitaro com comprimento maior que $L$ e sem visitar a mesma cidade mais de uma vez. Caso contrário, escreva 0.
Restrições
- $2 \le N \le 100\,000$.
- $1 \le M \le 200\,000$.
- $1 \le A_i < B_i \le N$ ($1 \le i \le M$).
- $1 \le C_i \le 1\,000\,000\,000\ (=10^9)$ ($1 \le i \le M$).
- É possível ir de qualquer cidade a qualquer outra passando por algumas estradas.
Subtarefas
- (7 pontos) $M \le 40$.
- (15 pontos) $N \le 18$.
- (23 pontos) $M-N \le 13$.
- (35 pontos) Para quaisquer três cidades distintas $a,b,c$, existe um percurso da cidade $a$ à cidade $c$ sem passar pela cidade $b$.
- (20 pontos) Nenhuma restrição adicional.
Exemplos
Entrada 1
4 4 1 2 1 1 3 2 2 4 4 3 4 3
Saída 1
0
Observação
Neste exemplo, a distância mínima da cidade $1$ (casa de Bitaro) até a cidade $4$ (escola) é $5$.
Há dois percursos até a casa de Bitaro sem visitar a mesma cidade mais de uma vez.
- Um percurso de comprimento $5$ que passa pelas estradas $3\to1$, nessa ordem, e visita as cidades $4\to2\to1$, nessa ordem.
- Um percurso de comprimento $5$ que passa pelas estradas $4\to2$, nessa ordem, e visita as cidades $4\to3\to1$, nessa ordem.
Como não existe um percurso até a casa de Bitaro com comprimento maior que $5$ e sem visitar a mesma cidade mais de uma vez, escreva 0.
Este exemplo satisfaz as restrições de todas as subtarefas.
Entrada 2
4 4 1 2 1 1 3 3 2 4 4 3 4 3
Saída 2
1
Observação
Neste exemplo, a distância mínima da cidade $1$ (casa de Bitaro) até a cidade $4$ (escola) é $5$.
Há dois percursos até a casa de Bitaro sem visitar a mesma cidade mais de uma vez.
- Um percurso de comprimento $5$ que passa pelas estradas $3\to1$, nessa ordem, e visita as cidades $4\to2\to1$, nessa ordem.
- Um percurso de comprimento $6$ que passa pelas estradas $4\to2$, nessa ordem, e visita as cidades $4\to3\to1$, nessa ordem.
Como existe um percurso até a casa de Bitaro com comprimento maior que $5$ e sem visitar a mesma cidade mais de uma vez, escreva 1.
Este exemplo satisfaz as restrições de todas as subtarefas.
Entrada 3
3 4 1 2 1 1 2 2 1 3 3 1 3 3
Saída 3
0
Observação
Este exemplo satisfaz as restrições das subtarefas 1, 2, 3 e 5.
Entrada 4
4 5 1 2 1 1 3 2 2 4 4 3 4 3 2 3 1
Saída 4
1
Observação
Este exemplo satisfaz as restrições de todas as subtarefas.
Entrada 5
12 17 2 4 656247308 4 6 106088453 1 5 754343261 9 12 497827261 3 8 759830309 3 4 61084725 1 6 324702188 3 6 415317430 7 12 846175092 5 8 278621369 1 10 891247646 10 12 755236904 6 8 511967203 5 6 597197970 1 7 800309458 7 9 348347831 10 11 134217757
Saída 5
0
Observação
Este exemplo satisfaz as restrições das subtarefas 1, 2, 3 e 5.