SPOJ Brasil

Os pesquisadores do departamento de pesquisa operacional da Universidade da Columbia Britânica foram contratados para uma estranha tarefa. Vários países da África resolveram se unir e utilizar oficialmente o meio de transporte que ficou mundialmente conhecido nos filmes do Tarzan: o cipó. Há milhões de cipós na África e é surpreendente com que velocidade e eficiência uma pessoa pode se deslocar na selva utilizando esse meio de transporte. Só surgiu um pequeno problema. Os cipós são dominados por três grandes tribos: os makelelês, os malouhdás e os abedis. As tribos exigem ser pagas por cipó usado no sistema de transporte. Como eles ainda não sabem o significado de palavras como cartel, cada uma fez o seu preço, e divergiram bastante. Enquanto os makelelês exigem 1235 bongôs por cipó usado, os malouhdás exigem 8977 e os abedis 10923 (a Jane ainda está viva, e ajudou a intermediar a negociação para esta tribo).

Os pesquisadores foram contratados para escolher os cipós que comporão o primeiro sistema cipoviário do mundo. Os contratantes construíram milhões de "pontos de cipó" pela selva africana e desejam que os cipós sejam escolhidos de tal forma que seja possível ir de qualquer ponto a qualquer outro usando os cipós contratados (você pode ter de trocar de cipó algumas vezes, como fazia o Tarzan). Você deve dizer qual o custo de um sistema que atenda estes requisitos e seja o mais barato possível.

Você pode supor que existam cipós suficientes na selva para que sempre exista um sistema cipoviário que atenda os requisitos.

Entrada

A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 1000) e m (1 <= m <= 2000000), onde n é o número de "pontos de cipó" e m é o número de cipós. Cada uma das m linhas seguintes contém três inteiros u, v e c indicando que existe um cipó que vai do ponto u e até o ponto v com custo c, onde 1 <= u, v <= n e c = 1235 ou 8977 ou 10923.

A entrada termina com final de arquivo.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima o custo de um sistema que atenda os requisitos descritos acima.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada:
3 3
1 2 10923
1 3 1235
2 3 1235
3 2
1 2 1235
2 3 10923

Saída:
Instancia 1
2470

Instancia 2
12158