Trouver le chemin le plus court 2

On vous fournit une carte composée de n villes et de m routes bidirectionnelles reliant ces villes. Chaque route possède une longueur entière non négative, notée . Votre objectif est de déterminer la longueur du chemin le plus court entre la ville 1 et la ville n.

Entrée

La première ligne contient deux entiers séparés par un espace, n et m (), qui représentent respectivement le nombre de villes et le nombre de routes.

Les m lignes suivantes contiennent chacune trois entiers séparés par un espace : , et , indiquant qu’il existe une route entre les villes et avec une longueur de ().

Sortie

Affichez un seul entier représentant la longueur du chemin le plus court reliant la ville 1 à la ville n.

Exemples