Descrição
Depois de estudar o final de semana todo, Samanta só conseguiu acordar na Segunda-feira após seu gato “Tom” fazer uma incrível peripécia maldosa, acertando-a em cheio após pular de cima do guarda roupa (A se pego esse gato !!!!). Quando Samanta olhou no relógio, deu um pulo tão grande que quase bateu a cabeça no teto, pois já era 7hs e a sua primeira prova da semana na Fatec SJC ia começar em 10 minutos. Sem mais delongas ela jogou a carteirinha do ônibus em cima da comoda, pegou sua mochila pesada de livros e a chave de seu potente Fusca para “voar” até a faculdade.
Entrou no carro, jogou outros dois gatos dorminhocos pra fora dele, fez cara de mau e girou a chave do Fusca e… (failure), girou novamente e... (failure), tentou novamente e… (failure). Já que o Fusca não dava partida ela correu até o quarto, guardou a chave do Fusca e foi obrigada a pegar a chave de seu outro carro, uma Ferrari conversível simples (tudo para não perder a prova né).
Enquanto o portão eletrônico da garagem se abria, ela pegou um mapa da cidade para ver qual a rota que deveria seguir para chegar mais rápido na faculdade. Quando olhou todos aqueles caminhos ficou super desesperada sem saber por onde ir, então olhou para frente e viu você, seu vizinho recém formado, passeando com seus dois animais de estimação, o Pig e o Cat. Ela correu até você e te implorou para que a ajudasse a achar esse caminho, será que você consegue ajudar a menina a não perder a prova?
Entrada
A primeira linha de cada caso de teste contém dois inteiro N e M (2 <= N <= 104 e 0 <= M <= 5 * 104), que representam respectivamente o número total de pontos e de ruas do mapa. Os pontos são identificados por inteiros de 1 a N. Cada rua liga dois pontos distintos, e há no máximo uma rua entre cada par de pontos. Cada uma das M linhas seguintes contém três inteiros P1, P2 e K (1 <= P1, P2 <= N e 0 <= K <= 104 ), representando respectivamente que tem uma rua de mão dupla ligando o ponto P1 ao ponto P2 e que a rua tem K quilômetros. Samanta está no ponto 1 do mapa e a Fatec no ponto N.
Saída
Uma única linha deve ser impressa, contendo um único inteiro, a distância mínima que Samanta deve percorrer para ir da sua casa (ponto 1) até a faculdade (ponto N), se não existir um caminho para ela ir deve ser impresso o valor -1.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
4 3 |
-1 |
|
4 4 |
9 |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Marcos Vinicius Costa Bustamante | Adaptado por Erich Rodrigues | Competição: FATEC SJC - Maratona interna 2015