Deuxième plus court chemin
On dispose de
n villes et de m routes bidirectionnelles reliant ces villes. Chaque route a une longueur correspondante . Emil, un voyageur intrépide, souhaite se rendre de la ville 1 à la ville n en empruntant ces routes. Toutefois, il ajoute une contrainte particulière à son périple : il choisira l’itinéraire le plus court parmi tous ceux qui sont strictement plus longs que le plus court chemin existant.En d'autres termes, votre tâche consiste à aider Emil à déterminer la longueur du deuxième plus court chemin reliant la ville
1 à la ville n.Input
La première ligne de l'entrée contient deux entiers
n et m, qui représentent respectivement le nombre de villes et le nombre de routes.
Les m lignes suivantes contiennent chacune trois entiers , et , indiquant qu'il existe une route bidirectionnelle entre la ville et la ville , de longueur .Output
Vous devez afficher un seul entier représentant la longueur du deuxième plus court chemin entre la ville
1 et la ville n.Examples
Entrée | Sortie |
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