El robot C-3BA, en su jornada por reparar robots en los confines de la Tierra, necesita ir desde una punta a otra de una isla del Caribe.

Existen ~n~ ciudades en la isla del Caribe, y hay ~m~ rutas bidireccionales entre ellas, la ~i~-ésima ruta conecta las ciudades ~u_i~ y ~v_i~, y tiene longitud ~w_i~.

Se garantiza que un par de ciudades está conectada por a lo más una ruta, que ninguna ruta conecta una ciudad consigo misma y que se puede ir desde cualquier ciudad a cualquier otra siguiendo una secuencia de rutas.

C-3BA necesita ir desde la ciudad ~a~ la ciudad ~b~, se garantiza que ~a~ y ~b~ son diferentes.

Recientemente, debido al cambio climático, alguna ruta podría incendiarse, no se puede pasar por una ruta incendiada.

A C-3BA le gustaría conocer, cuántas rutas ~x~ existen tal que, si la ruta ~x~ se incendia, y no se incendia más ninguna ruta, la longitud del camino mínimo desde ~a~ hasta ~b~ difiere con respecto a si no se hubiera incendiado ninguna ruta.

Note que la longitud del camino mínimo de ~a~ a ~b~ es igual a la menor suma de las longitudes de alguna secuencia de rutas que vaya desde ~a~ hasta ~b~.

Subtareas

• Subtarea 1 (10 puntos): ~m = n - 1~ y la ~i~-ésima ruta va de la ciudad ~i~ a la ciudad ~i+1~ para todo ~1 \leq i < n~, ~n \leq 100~ y ~w_i = 1~ para todo ~i~.

• Subtarea 2 (20 puntos): ~m = n - 1~, es decir, las rutas forman un árbol, ~n \leq 100~ y ~w_i = 1~ para todo ~i~.

• Subtarea 3 (20 puntos): ~n \leq 500~, ~m \leq 1000~.

• Subtarea 4 (25 puntos): ~n \leq 500~, ~m \leq 10000~.

• Subtarea 5 (25 puntos): Sin restricciones adicionales.

Entrada

En la primera línea de entrada, dos enteros ~n~ ~(2 \leq n \leq 10^5)~ y ~m~ ~(1 \leq m \leq 2\cdot 10^5)~, la cantidad de ciudades y rutas respectivamente.

En la segunda línea de entrada, dos enteros ~a~ y ~b~, la ciudad de inicio y de final respectivamente.

En cada una de las siguientes ~m~ líneas, tres enteros ~u_i~, ~v_i~ y ~w_i~ ~(1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq w_i \leq 10^9)~, indicando que existe una ruta bidireccional entre las ciudades ~u_i~ y ~v_i~ con longitud ~w_i~.

Salida

Imprima un solo entero en una línea, la cantidad de rutas ~x~ tal que si ~x~ se incendia, y no se incendia más ninguna ruta, la longitud del camino mínimo desde ~a~ hasta ~b~ difiere con respecto a si no se hubiera incendiado ninguna ruta.

Ejemplo de Entrada

7 9
1 7
1 2 2
1 3 1
2 4 1
2 5 1
3 4 2
3 7 10
4 6 5
4 7 8
6 7 2

Ejemplo de Salida

2

Nota

Las rutas que si se incendian la longitud del camino mínimo de ~1~ a ~7~ aumenta son la ruta que va de la ciudad ~4~ a la ~6~ y la que va de la ~6~ a la ~7~.