Il secondo percorso più breve
Sono date
n città e m strade bidirezionali che le collegano. Ogni strada ha una lunghezza corrispondente . Emil, un viaggiatore avventuroso, vuole andare dalla città 1 alla città n percorrendo queste strade. Tuttavia, ha in mente una variante particolare: cercherà il percorso più breve tra quelli che sono strettamente più lunghi rispetto al tragitto minimo complessivo.In altre parole, il tuo compito è aiutare Emil a determinare la lunghezza del secondo percorso più breve dalla città
1 alla città n.Input
La prima riga dell’input contiene due interi
n e m, che rappresentano rispettivamente il numero di città e il numero di strade.
Le successive m righe contengono tre interi , e , i quali indicano che esiste una strada bidirezionale tra le città e , con lunghezza .Output
Stampa un singolo intero che rappresenti la lunghezza del secondo percorso più breve dalla città
1 alla città n.Esempi
Ingresso | Uscita |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB