Revoltas e Rotas

Num país com n cidades, existem m estradas que as ligam. Cada estrada tem uma probabilidade (0 ≤ ≤ 1) de estar aberta, devido a motins em curso. As cidades, por sua vez, estão sempre abertas. O seu objetivo é encontrar o percurso que vá da cidade 1 até à cidade n e que maximize a probabilidade de todo o trajeto estar disponível, tendo em conta as probabilidades atribuídas a cada estrada. Se não existir qualquer caminho entre a cidade 1 e a cidade n, a probabilidade deve ser considerada 0.

Escreva um programa para determinar a probabilidade máxima de um percurso aberto entre a cidade 1 e a cidade n.

Entrada

A primeira linha contém dois inteiros separados por espaço, n e m (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000), que representam, respetivamente, o número de cidades e o número de estradas.

As próximas m linhas contêm três inteiros separados por espaço, , e (1 ≤ ai, bi ≤ n, 0 ≤ pi ≤ 1), que definem uma estrada entre as cidades $$aibipi$$** de essa estrada estar aberta.

Saída

Imprima um único número real, que represente a probabilidade máxima de existir um percurso aberto entre as cidades 1 e n. A sua resposta será aceite se diferir da correta em, no máximo, 1e-5.

Exemplos