Juan vive en una ciudad con ~N~ estaciones (numeradas del ~1~ al ~N~). Hay ~M~ ferrocarriles (numerados del ~1~ al ~M~). El ferrocarril ~i~ ~(1 \le i \le M)~ conecta la estación ~A_i~ y la estación ~B_i~ en ambas direcciones, y la tarifa es de ~C_i~ pesos. Juan vive cerca de la estación ~S~ y va a la escuela cerca de la estación ~T~. Planea comprar un pase de tren que conecte estas dos estaciones. Cuando compra un pase de tren, debe elegir una ruta entre la estación ~S~ y la estación ~T~ con el costo mínimo. Usando este pase de tren, puede tomar cualquier ferrocarril contenido en una ruta elegida en cualquier dirección sin costos adicionales. Juan a menudo va a librerías cerca de la estación ~U~ y la estación ~V~. Por lo tanto, quiere comprar un pase de tren para que el costo desde la estación ~U~ hasta la estación ~V~ se minimice. Cuando se mueve de la estación ~U~ a la estación ~V~, primero elige una ruta desde la estación ~U~ hasta la estación ~V~. Luego, la tarifa que tiene que pagar es:

• ~0~ pesos si el ferrocarril ~i~ está contenido en una ruta elegida cuando compra un pase de tren.
• ~C_i~ pesos si el ferrocarril ~i~ no está contenido en una ruta elegida cuando compra un pase de tren. La suma de las tarifas anteriores es el costo desde la estación ~U~ hasta la estación ~V~. Quiere saber el costo mínimo desde la estación ~U~ hasta la estación ~V~ si elige una ruta adecuada cuando compra un pase de tren.

Tarea

Escriba un programa que calcule el costo mínimo desde la estación ~U~ hasta la estación ~V~ si elige una ruta adecuada cuando compra un pase de tren.

Entrada

Lea los siguientes datos desde la entrada estándar:

• La primera línea de entrada contiene dos enteros separados por espacio ~N~, ~M~. Esto significa que la ciudad en la que vive Juan tiene ~N~ estaciones y ~M~ ferrocarriles.
• La segunda línea contiene dos enteros separados por espacio ~S~, ~T~. Esto significa que Juan planea comprar un pase de tren desde la estación ~S~ hasta la estación ~T~.
• La tercera línea contiene dos enteros separados por espacio ~U~, ~V~. Esto significa que Juan quiere minimizar el costo desde la estación ~U~ hasta la estación ~V~.
• La i-ésima línea ~(1 \le i \le M)~ de las siguientes ~M~ líneas contiene tres enteros separados por espacio ~A_i~, ~B_i~, ~C_i~. El ferrocarril ~i~ conecta la estación ~A_i~ y la estación ~B_i~ en ambas direcciones, y la tarifa es de ~C_i~ pesos.

Salida

Escriba una línea en la salida estándar. La salida debe contener el costo mínimo desde la estación ~U~ hasta la estación ~V~ si elige una ruta adecuada cuando compra un pase de tren.

Restricciones

Todas las entradas cumplen las siguientes condiciones:

• ~2 \le N \le 100 000~.
• ~1 \le M \le 200 000~.
• ~1 \le S \le N~.
• ~1 \le T \le N~.
• ~1 \le U \le N~.
• ~1 \le V \le N~.
• ~S \neq T~.
• ~U \neq V~.
• ~S \neq U~ o ~T \neq V~.
• Juan puede moverse desde cualquier estación a cualquier otra estación tomando ferrocarriles.
• ~1 \le A_i < B_i \le N~ ~(1 \le i \le M)~.
• Para cada ~(1 \le i < j \le M)~, sea ~A_i \neq A_j~ o ~B_i \neq B_j~.
• ~1 \le Ci \le 1 000 000 000~ ~(1 \le i \le M)~.

Subtareas

• Subtarea 1 [16 puntos]: ~S = U~.
• Subtarea 2 [15 puntos]: Existe una ruta única y de mínimo coste desde la estación ~S~ hasta la estación ~T~.
• Subtarea 3 [24 puntos]: ~N \le 300~.
• Subtarea 4 [45 puntos]: No hay restricciones adicionales.

Ejemplo de Entrada

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

Ejemplo de Salida

2

En este ejemplo de entrada, solo hay una ruta que Juan puede elegir cuando compra un pase de cercanías:
Estación 1 → Estación 2 → Estación 3 → Estación 5 → Estación 6.

Para minimizar el costo desde la estación 1 a la estación 4, elige la siguiente ruta:
Estación 1 → Estación 2 → Estación 3 → Estación 5 → Estación 4.

Cuando elige esta ruta, la tarifa que debe pagar es:

• 2 pesos por el ferrocarril 5 que conecta la estación 4 y la estación 5, y
• 0 pesos para otros ferrocarriles. Por tanto, el coste total es de 2 pesos.