Viagem do Flúcio

Existem vários algoritmos conhecidos para encontrar o menor caminho de um local para o outro. Temos GPS em nossos carros e em nossos celulares para nos mostrar o caminho mais rápido para onde nós quisermos ir. Flúcio gosta de viajar lentamente pois gosta de apreciar a estrada enquanto come um delicioso pão. Ajude Flúcio à encontrar o maior caminho entre a sua cidade e a de destino sem passar por uma cidade mais de uma vez.

Um caminho consiste em uma sequência de cidades distintas $c_1,c_2,\cdots,c_k$, tais que existe uma rota de $c_i$ para $c_{i+1}$ para todo $1 \leq i < k$.

Entrada

A primeira linha da entrada contém dois inteiros $n, m$ $(2 \leq n \leq 18; 1 \leq m \leq n^2 - n)$ o número de cidades e o número de estradas conectando as cidades. Existe no máximo uma estrada entre qualquer par de cidades. As cidades são numeradas de $0$ à $n - 1$, sendo $0$ a cidade de Flúcio e $n - 1$ a cidade de destino.

As próximas $m$ linhas contém cada uma três inteiros $s, d, l$ indicando uma estrada entre as cidades $s$ e $d$ de tamanho $l$ km$(0\leq s \leq n - 1;0\leq d\leq n - 1; s \neq d; 1\leq l \leq 10 000)$. Cada estrada possuí mão dupla. Sempre existe um caminho de $0$ à $n - 1$.

Saída

Seu código deve imprimir um único inteiro, o tamanho do maior caminho que começa na cidade $0$, termina na cidade $n - 1$, e não visita qualquer cidade mais de uma vez. O tamanho do caminho é a soma dos tamanhos das estradas no caminho.

ENTRADA	SAÍDA
3 3 0 2 5 0 1 4 1 2 3	7