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 |
