Problem I
Intelligence Exchange

Even though they are still high school students, Carmen and Juni are already top-tier spies.

Carmen and Juni live in Byteland, which can be modeled as an undirected connected graph with $n$ vertices and $m$ edges. Today morning at exactly 08:00 am, Carmen goes from her house at vertex $h_ c$ to her school located at vertex $s_ c$. Also at exactly 08:00 am, Juni also goes from his house at vertex $h_ j$ to his school located at vertex $s_ j$.

On the way to school today, Carmen and Juni want to exchange their gathered intelligence. As top-tier spies, they only need to be at the same location (either at a vertex or on an edge) at some moment in time in order to exchange intelligence.

For simplicity, we will assume that Carmen and Juni will stay at their schools forever after arriving at their schools. This also means that after arriving at their schools, Carmen and Juni can wait there and exchange intelligence at a later time.

However, Carmen and Juni have no time to waste — they always use a shortest path to go from their houses to their schools. If there are multiple shortest paths, Carmen and Juni are happy to choose any of them.

Carmen and Juni want to know, what is the number of different locations they can exchange intelligence. Note that if they can meet at the same location at two different points of time, it should be counted only once. If they can meet at two different locations on one edge, both locations should be counted.

Input

The input contains multiple test cases. Each test case is presented as below:

• The first line contains two integers $n$ and $m$ $(1 \le n, m \le 5 \cdot 10^5)$.

• The second line contains four integers $h_ c$, $s_ c$, $h_ j$ and $s_ j$ $(1 \le h_ c, s_ c, h_ j, s_ j \le n; h_ c \neq s_ c; h_ j \neq s_ j)$.

• In the next $m$ lines, the $i$-th line contains three integers $u$, $v$ and $t$ $(1 \le u, v \le n; u \neq v; 1 \le t \le 10^9)$, meaning there is an edge connecting $u$ and $v$, and it takes either Carmen and Juni $t$ minutes to go through this edge. It is guaranteed that the graph is connected.

Note that Carmen and Juni have exact same speed. Furthermore, their speed do not change. So if it takes $t$ minutes to go through an edge with length $\ell $, it will take them exactly $x \cdot t$ minutes to go through $x \cdot \ell $ of this edge for any $x$ between $0$ and $1$.

The input terminates with two $0$s, and you don’t have to process this case.

The sum of $n$ in all test cases does not exceed $5 \cdot 10^5$. The sum of $m$ in all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, let $r$ be the number of different locations Carmen and Juni can exchange intelligence. If $r > 10^9$, print a single line containing $-1$. Otherwise, print a single line containing $r$.

Explanation of the sample input

The figure on the left shows the first test case. Carmen’s house and school are at vertices $1$ and $3$, respectively. Juni’s house and school are at vertices $4$ and $5$, respectively. There are two shortest paths with length $30$ from Carmen’s house to her school. There are two shortest paths with length $40$ from Juni’s house to his school. They can meet at vertex $2$ at 08:10 am if Carmen uses the path $1 \rightarrow 2 \rightarrow 3$ (shown in red) and Juni uses the path $4 \rightarrow 2 \rightarrow 5$ (shown in blue).

The figure on the right shows the second test case. There is only one shortest path with length $20$ from Carmen’s house to her school: $1 \rightarrow 3$. It is not possible for the two to meet.

In the third test case, both Carmen and Juni’s schools are at vertex $3$. Carmen arrives at her school at 08:10 am and Juni arrives at his school at 08:20 am. Carmen can wait at school until Juni arrives, and exchange intelligence at 08:20 am.

5 6
1 3 4 5
1 2 10
2 3 20
1 3 30
4 2 10
2 5 30
4 5 40
5 6
1 3 4 5
1 2 10
2 3 20
1 3 20
4 2 10
2 5 30
4 5 40
3 2
1 3 2 3
1 3 10
2 3 20
0 0

1
0
1