uCoder | 1094 | Nível: 5 | Tempo Limite: 10
Turismo em Ecaterimburgo
Adaptado por Erich Rodrigues
Competição: USP - Seletiva para Maratona de Programação, 2013
Muitos podem pensar: “O que vou fazer em Ecaterimburgo? Essa cidade é no fim do mundo!!!”. Entretanto, muitas coisas interessantes ocorreram na cidade, possuindo vários monumentos e locais históricos. Para citar alguns, Ecaterimburgo tem um monumento que é um grande teclado de computador localizado na beira do rio Izet; um monumento a Michael Jackson (!!); na mansão Ipatiev foram assassinados os Romanovs (o czar Nicolau, sua esposa, quatro filhas e filho); lá houve um vazamento de antraz em 1979; um piloto de U2 americano foi capturado e condenado por espionagem; entre outros. Ou seja, existe muito a fazer nos dias em que a cidade for visitada.
A central de turismo de Ecaterimburgo, construiu um mapa com as principais atrações turísticas da cidade, assim como os belos passeios ligando esses caminhos. Esse mapa também mostra um nível de dificuldade de cada passeio (relacionado a duração, pavimentação da via, relevo etc.) e o sentido no qual ele deve ser feito. Eles desejavam construir uma rota que passasse por todas as atrações turísticas e os passeios. Foi idealizado, então, um concurso que visava fazer esta rota e, ao mesmo tempo, homenageava uma das cidades irmãs de Ecaterimburgo: Caliningrado, cujo nome até o final da segunda guerra mundial era Konigsberg. A ideia era construir uma rota em que se partisse de uma das atrações, e passando por todos os passeios se retornasse ao ponto de partida. Sabemos que, como no caso das pontes de Konigsberg, nem sempre é possível construir uma rota assim. Por isso a central permitiu que, se necessário, os passeios poderiam ser feitos mais de uma vez. No entanto, ela exigiu que a dificuldade total da rota (soma das dificuldades de cada passeio multiplicado pelo número de vezes que ele é feito) fosse mínima. Dessa forma, o concurso consistia de propor, a partir de uma rota inicial, quais passeios deveriam ser percorridos mais de uma vez e quandas vezes, para se obter uma rota como a desejada pela central.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
A primeira linha de cada instância contém dois inteiros N e M , o número de atrações da cidade e o número de passeios respectivamente. As próximas M linhas contém três inteiros, ai , bi , di indicando que o passeio i começa em ai , termina em bi e tem dificuldade di .
A entrada deve ser lida da entrada padrão.
Saída
Para cada instância imprima a dificuldade total mínima da rota desejada. Se for impossível obter uma rota da forma desejada, imprima impossivel.
A saída deve ser escrita na saída padrão.
Restrições
• 2 ≤ N ≤ 50
• 0 ≤ M ≤ N^2 + 10^3
• 1 ≤ ai , bi ≤ N
• 1 ≤ di ≤ 3 × 10^4
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
2 2 |
40000 |