SPOJ Brasil

Albert Einstein nasceu na Alemanha, mas foi na Suíça, trabalhando como funcionário público, que escreveu em 1905 os trabalhos que revolucionaram a Física moderna e o tornaram famoso. Em 1921 ganhou o prêmio Nobel de Física pela descoberta da lei do efeito fotoelétrico. Muitos acham seus trabalhos sobre a Teoria da Relatividade os mais importantes de sua carreira, entretanto não foram os que renderam o valioso prêmio.

Einstein gostava muito de fazer "experimentos mentais" para avaliar suas teorias. Um desses experimentos é muito famoso e descreve um elevador caindo com um relógio dentro. A idéia de viagens no tempo acabaram surgindo como possíveis, desde que se descobrisse como construir máquinas que pudessem viajar em velocidades maiores do que a velocidade da luz. Certamente, num futuro não muito distante, isso será possível e poderemos viajar livremente entre as eras e ver eventos como o descobrimento do Brasil em 1500, a chegada da Família Real em 1808 ou o Corinthians campeão da Libertadores em 2962 ao vivo.

Com as constantes viagens no tempo, será importante regular o serviço. As máquinas do tempo estarão espalhadas por toda a História e os viajantes terão de pegá-las para viajar para o presente ou para o futuro. Devido a restrições técnicas destas máquinas, não será possível viajar para qualquer instante do tempo diretamente, mas apenas para outros momentos históricos, de onde uma nova máquina poderá ser usada para seguir viagem. No entanto, estando em um momento histórico, você consegue ir para qualquer outro momento viajando por uma ou mais máquinas.

Juntamente com os viajantes do tempo, também surgirão os piratas da História, que tentarão roubar tesouros, inverter acontecimentos e mudar a história com os objetivos mais maldosos. Isso acarretará na criação da Polícia do Tempo. No ano de 2850 (antes do Corinthians ganhar sua primeira Libertadores) a Polícia do Tempo resolve isolar acontecimentos históricos, desabilitando ligações entre algumas máquinas. Cada ligação tem um custo associado para ser desabilitado, e sua tarefa é encontrar, dado um conjunto de momentos históricos, um conjunto de ligações -- de custo mínimo -- que ao serem desconectadas isolam os acontecimentos, ou seja, estando em uma máquina não será possível viajar para algumas das outras máquinas.

Entrada

A primeira linha de cada instância contém dois inteiros N e M (1 ≤ N ≤ 100 e 1 ≤ M ≤ N(N-1)/2) indicando o número de máquinas e o número de ligações, respectivamente. Cada uma das M linhas seguinte possui três inteiros u, v e c (1 ≤ u, v ≤ N, 1 ≤ c ≤ 100) que representam a existência de uma ligação entre a máquina u e v com custo c. Tal ligação pode ser usada para viajar da máquina u para máquina v e também da máquina v para máquina u.

Saída

Para cada instância imprima uma linha contendo a soma dos custos das ligação que devem ser removidas.

Exemplo de entrada
3
5 6
1 2 1
1 3 1
2 3 1
3 4 10
3 5 1
4 5 1
4 4
1 2 10
2 3 5
3 4 20
4 1 50
3 2
1 2 1
2 3 2

Exemplo de saída
2
15
1