XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: museu.x, onde x deve ser c, cpp, java, js ou py

Museu

Desde que o arquiteto Frank Gehry projetou o Museu Guggenheim de Bilbao, os museus têm sido construídos com formas cada vez mais complexas, fugindo de padrões pré-estabelecidos e de simetrias. Um típico museu moderno é composto por um conjunto de salas ligadas por corredores e escadas, sem preocupação com a pré-definição de caminhos a serem seguidos pelas pessoas.

Henriqueta é uma professora do ensino fundamental que deseja visitar o museu da Ordem Brasileira de Medicina (OBM) para mostrar aos seus alunos de ciências como o corpo humano funciona e como as cirurgias eram feitas nos séculos XIX e XX. Henriqueta quer planejar uma visita pelas salas do museu, obedecendo às seguintes restrições:

  • a visita deve começar e terminar em uma mesma sala;
  • exceto a sala de partida, nenhuma sala do museu pode ser visitada mais de uma vez;
  • a visita deve incluir pelo menos duas salas;
  • os corredores são unidirecionais, ou seja, as pessoas podem caminhar, em um corredor, apenas em uma direção.
  • a visita deve tomar o menor tempo possível.

Um estudo preliminar, realizado pelo próprio museu, indica o tempo médio que cada visitante fica em uma sala e quanto tempo demora para atravessar um corredor ou uma escada. Henriqueta quer a sua ajuda para calcular o tempo total da menor visita que ela pode efetuar, obedecendo às restrições dadas.

Escreva um programa que, dados um conjunto de salas, um conjunto de corredores e escadas que ligam essas salas e o tempo necessário para percorrer cada sala e cada corredor, determine qual é o menor tempo possível para uma visita. Note que o tempo de visita da sala onde a visita se inicia deve ser contado apenas uma vez.

Entrada

A primeira linha da entrada contem dois inteiros S e C, que indicam, respectivamente, o número de salas e o número de corredores. As salas são numeradas de 1 a S. Cada uma das C linhas seguintes descreve um corredor ou escada. A descrição é composta por três inteiros, I, F e T, indicando que o corredor somente pode ser percorrido da sala I para a sala F no tempo T.

Saída

Seu programa deve imprimir uma única linha contendo o tempo gasto na visita de menor duração que Henriqueta pode realizar no museu. Existe pelo menos uma visita que atende às restrições impostas.

Restrições

  • 1 ≤ S ≤ 1000
  • 1 ≤ C ≤ 1000
  • 1 ≤ I ≤ N
  • 1 ≤ F ≤ N
  • 1 ≤ T ≤ 1000
  • O tempo total máximo é sempre menor ou igual a 1 000 000.

Exemplos

Entrada
2 2
1 1
1 2 1
2 1 3
Saída
6
Entrada
5 6
5 5 10 10 5
1 2 1
2 3 1
5 1 1
3 4 1
4 1 1
5 2 1
Saída
34
Entrada
8 10
3 10 8 4 1 1 8 1
1 2 1
1 3 10
4 1 1
5 8 1
3 7 1
7 5 2
8 4 2
2 3 2
3 6 1
6 7 2
Saída
42
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação