Trova il Percorso Più Breve 3
Ti viene fornita una mappa composta da
n città e m strade bidirezionali che collegano queste città. Ogni strada ha una lunghezza intera non negativa, indicata con . Il tuo compito è determinare la lunghezza del percorso più breve tra la città 1 e la città n.Input
La prima riga contiene due interi separati da spazio,
n e m (), che rappresentano il numero di città e il numero di strade, rispettivamente.Le successive
m righe contengono ciascuna tre interi separati da spazio , e , che descrivono una strada tra le città e con lunghezza ().Output
Devi stampare un unico intero che rappresenti la lunghezza del percorso più breve tra la città
1 e la città n.Esempi
Esempio di Input | Esempio di Output |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB