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

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

Frete

O senhor Satoshi passou anos reclamando da empresa de correios do seu país, porque ela sempre transportava suas encomendas usando um caminho que passava pelo número mínimo de cidades entre a cidade onde o senhor Satoshi mora e a cidade destino da encomenda. A empresa alegava que essa estratégia levava ao menor tempo para a entrega final da encomenda. O problema é que ele notou que essa estratégia da empresa nem sempre levava ao menor preço para o frete total. Se ele pudesse escolher o caminho por onde a encomenda deveria passar para ir da sua cidade para a cidade destino, ele poderia economizar bastante com o frete, já que não havia muita urgência para a maioria de suas encomendas.

Depois de muita reclamação, a empresa finalmente está dando aos clientes a opção de determinar o caminho por onde a encomenda deve passar. O senhor Satoshi, feliz da vida, agora quer a sua ajuda para implementar um programa que, dado o custo de transporte de uma encomenda entre vários pares de cidades pelo país, para os quais a empresa realiza entregas diretas, determine qual é o preço total mínimo para o frete entre a cidade onde ele mora e a cidade destino da encomenda.

O país tem N cidades, identificadas pelos números de 1 a N. O senhor Satoshi mora na cidade 1 e o destino da encomenda será sempre a cidade N. É garantido que sempre haverá um caminho de 1 até N. No exemplo da figura, para N=5, o custo mínimo será 7, para o caminho 1 → 2 → 4 → 5.

Entrada

A primeira linha da entrada contém dois números inteiros N e M, representando o número de cidades e quantos pares de cidades possuem entrega direta de encomenda pela empresa. As M linhas seguintes contêm, cada uma, três inteiros A, B e C, indicando que a empresa realiza a entrega de uma encomenda diretamente entre as cidades A e B, cobrando o preço C.

Saída

Seu programa deve imprimir uma linha contendo um inteiro representando o preço mínimo total para o frete entre a cidade onde o senhor Satoshi mora, a cidade 1, e a cidade destino da encomenda, a cidade N.

Restrições

  • 2 ≤ N ≤ 100 e 1 ≤ M ≤ 1000
  • 1 ≤ A,B ≤ N e A ≠ B
  • 1 ≤ C ≤ 1000

Exemplos

Entrada
5 6
1 2 4
1 3 3
4 3 6
4 5 2
2 4 1
3 5 5
Saída
7
	

 

Entrada
7 10
1 2 5
3 1 32
1 4 3
2 3 4
2 6 20
6 3 1
6 4 9
6 5 6
3 7 18
5 7 2
Saída
18
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação