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.