这个周末市中心非常繁忙。Javad 和 Jalal 正在各自组织一场比赛，分别是 JavadRally 和 JalalRally。他们已经确定了每场比赛的起点和终点交叉路口，现在正在与当地警方协商以确定每场比赛的路线。比赛当天，警方将封闭每条路线上的所有交叉路口，因此两条路线不能有任何公共交叉路口。此外，由于比赛路线在当天被封闭会导致市中心交通更加拥堵，每条路线都必须是其起点到终点的最短路径。他们难以确定合适的无冲突路线，因此请求你帮助计算组织这两场比赛的不同方案数。如果两场比赛的路线对不同，则视为不同的方案。

城市地图由 $n$ 个编号为 $1$ 到 $n$ 的交叉路口和连接这些路口的 $m$ 条道路组成。每条道路都有指定的长度。此外，每场比赛的起点和终点交叉路口均已给出。你需要计算不同无冲突最短路径比赛方案的数量。

输入格式

第一行包含两个整数 $n$ ($4 \le n \le 24$) 和 $m$ ($1 \le m \le \frac{n(n - 1)}{2}$)。接下来的 $m$ 行描述道路。第 $i$ 条道路包含三个整数：$u_i$ ($1 \le u_i \le n$)，$v_i$ ($1 \le v_i \le n$) 和 $w_i$ ($1 \le w_i \le 1000$)，分别表示其两个端点和长度。给定地图中没有自环和重边，且所有道路都是双向的。最后一行包含 $4$ 个整数：$s_1, t_1, s_2$ 和 $t_2$ ($1 \le s_1, t_1, s_2, t_2 \le n$)，分别表示 Javad 路线的起点和终点，以及 Jalal 路线的起点和终点。保证所有这些数字互不相同。保证给定地图是连通的，即任意两个交叉路口之间都存在路径。

输出格式

输出组织这两场比赛的不同方案数。

样例

样例输入 1

4 4
1 2 2
2 3 1
1 3 1
3 4 1
1 2 3 4

样例输出 1

1

样例输入 2

4 3
1 2 1
2 3 1
3 4 1
1 3 2 4

样例输出 2

0

样例输入 3

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

样例输出 3

3