Trova il Percorso Più Breve 2
Hai a disposizione una mappa composta da
n città e m strade bidirezionali che le collegano. Ogni strada ha una lunghezza intera non negativa indicata da . Il tuo compito è trovare la lunghezza del percorso più breve tra la città 1 e la città n.Dati in ingresso
La prima riga contiene due interi separati da uno spazio,
n e m (), che rappresentano rispettivamente il numero di città e il numero di strade.Le successive
m righe contengono ognuna tre interi separati da uno spazio: , e , che rappresentano una strada tra la città e la città con lunghezza ().Dati in uscita
Devi stampare un unico intero che corrisponde alla lunghezza del percorso più breve dalla città
1 alla città n.Esempi
Input | Dati in ingresso |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB