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