SPOJ Brasil

O prefeito, cujo apelido é “Guima”, de uma pequena cidade do interior de São Paulo decidiu organizar uma corrida para decidir quais cidadãos terão direito às vagas remanescentes no ICPC (Incontro Cemanal das Pessoa Carentes), evento no qual são distribuídas cestas básicas, entre outras coisas, aos participantes. Guima designou você e sua equipe para definir qual será o trajeto da corrida.

Na cidadezinha existem exatamente M ruas e N pontos turísticos. Cada uma das M ruas liga um par de pontos turísticos distintos. Todas as ruas são de mão dupla. Tudo muito simples!

Para dificultar a sua vida (ele adora fazer isso), Guima fez algumas exigências com relação ao trajeto. A quantidade de pontos turísticos distintos contidos no trajeto deve ser ímpar (no mínimo três). O trajeto deve ser fechado (começar e terminar no mesmo lugar), para que os espectadores assistam à largada e à chegada da corrida. Para não tornar enfadonha a jornada dos aspirantes a atletas, o trajeto não pode passar mais do que uma vez por um mesmo ponto turístico (com exceção do ponto inicial que coincide com o ponto final). O comprimento do trajeto deve ser o menor possível, afinal se trata de uma corrida de amadores. O comprimento de um trajeto é a soma dos comprimentos das ruas que os atletas terão que percorrer.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância é composta de diversas linhas. A primeira linha contém dois inteiros positivos N e M, sendo que N corresponde ao número de pontos turísticos da cidade, e M corresponde ao número de ruas. Os pontos da cidade são identificados por 1, 2, . . . , N. Cada uma das próximas M linhas contém uma tripla de inteiros positivos separados por um espaço, digamos u, v e c, indicando que a rua que liga os pontos turísticos u e v tem comprimento c.

Restrições

1 <= N <= 100
1 <= M <= (N2 - N)/2
1 <= u, v <= N
1 <= c <= 999

Saída

Para cada instância imprima um inteiro contendo o comprimento do trajeto, conforme especificado; ou a palavra impossivel, caso não exista um trajeto que atenda aos requisitos impostos pelo pseudodemograta Guima.

Exemplo de entrada

2
5 10
1 2 1
2 3 1
3 4 1
4 5 1
5 1 1
1 4 4
1 3 4
2 5 4
2 4 4
3 5 4
4 4
1 2 666
3 4 666
1 3 666
2 4 666

Saída para o exemplo de entrada

5
impossivel