Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

EINSTEIN - Viagens no tempo

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


Adicionado por:Wanderley Guimarăes
Data:2008-10-01
Tempo limite:0.307s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2013-04-04 11:39:37 luccasiau
Em 2012 morreu uma grande piada..

Last edit: 2013-04-04 12:05:46
2012-08-30 21:35:13 Vinicius Coelho [UFG]
"No ano de 2850 (antes do Corinthians ganhar sua primeira Libertadores)" vish UAEUAEHAEUHAEUHAEUE
2011-08-19 21:52:40 Marcos Daniel [UERN]
Alguém sabe dizer se pode haver mais de uma aresta entre 2 vertices ?
2010-06-23 16:37:07 Paulo Cezar [UFG]
A primeira linha é o número de casos de teste..
2010-06-21 14:22:51 Lafaiet Castro [CC-INF-UFG]
Essa entrada parece estar incorreta. O que seria esse "3" na primeira linha?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.