Raccourci (AB)
Problem
Une description du réseau routier du pays vous est donnée. Votre tâche – trouver la longueur du chemin le plus court entre les villes A et B.
Entrée
Le réseau routier est donné dans le fichier d'entrée comme suit : la première ligne contient les nombres N et K (1<=N<=100000, 0<=K<=300000), où K – nombre de routes. Chacune des lignes K suivantes contient une description d'une route à double sens – trois entiers ai, bi et li (1aibiN, 1li106). Cela signifie qu'il existe une route de longueur li qui mène de la ville ai à la ville bi. La dernière ligne contient deux nombres A et B – nombres de villes entre lesquelles il faut calculer la distance la plus courte (1<=A,B<=N )
Mentions légales
Vous devez sortir le numéro unique – distance entre les villes souhaitées. S'il est impossible de se rendre de la ville A à la ville B par la route, écrivez –1.
Exemples
| # |
Entrée |
Sortie |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |