Problem
Se le proporciona una descripción de la red de carreteras del país. Tu tarea – encuentre la longitud del camino más corto entre las ciudades A y B.
Entrada
La red de carreteras se proporciona en el archivo de entrada de la siguiente manera: la primera línea contiene los números N y K (1<=N<=100000, 0<=K<=300000), donde K – numero de caminos Cada una de las siguientes líneas K contiene una descripción de una carretera de doble sentido – tres enteros ai, bi y li (1aibiN, 1li106). Esto significa que hay un camino de longitud li que va de la ciudad ai a la ciudad bi. La última línea contiene dos números A y B – número de ciudades entre las que es necesario calcular la distancia más corta (1<=A,B<=N )
Impresión
Debe generar el número único – distancia entre las ciudades requeridas. Si es imposible llegar de la ciudad A a la ciudad B por carretera, escriba –1.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |