题目描述

“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。

比荷卢经济联盟有很多公交线路。

每天公共汽车都会从一座城市开往另一座城市。

沿途汽车可能会在一些城市（零或更多）停靠。

旅行社计划旅途从 $S$ 城市出发，到 $F$ 城市结束。

由于不同旅客的景点偏好不同，所以为了迎合更多旅客，旅行社将为客户提供多种不同线路。

游客可以选择的行进路线有所限制，要么满足所选路线总路程为 $S$ 到 $F$ 的最小路程，要么满足所选路线总路程仅比最小路程多一个单位长度。

现在给定比荷卢经济联盟的公交路线图以及两个城市 $S$ 和 $F$，请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $N$ 和 $M$，分别表示总城市数量和道路数量。

接下来 $M$ 行，每行包含三个整数 $A,B,L$，表示有一条单向线路从城市 $A$ 通往城市 $B$，长度为 $L$。

需注意，线路是单向的，存在从 $A$ 到 $B$ 的线路不代表一定存在从 $B$ 到 $A$ 的线路，另外从城市 $A$ 到城市 $B$ 可能存在多个不同的线路。

接下来一行，包含两个整数 $S$ 和 $F$，数据保证 $S$ 和 $F$ 不同，并且 $S$、$F$ 之间至少存在一条线路。

输出格式

每组数据输出一个结果，每个结果占一行，表示满足条件的路线总数（路线总长度等于最短路，或者等于最短路 +1）。

数据保证结果不超过 $10^9$。

样例

输入样例：

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

输出样例：

3
2

样例解释

第一个测试数据（图见原题描述或上方样例图）：

• 最短路长度为 $6$，有两条：$1 \to 2 \to 5$，$1 \to 3 \to 5$
• 次短路长度为 $7$，有一条：$1 \to 3 \to 4 \to 5$ 总共有 $3$ 条路线符合条件。

第二个测试数据： 城市数 $N=5$，道路数 $M=6$，$S=4$，$F=1$。

需要找出从 $4$ 到 $1$ 的最短路和次短路。

道路：

• $2 \to 3$ 长度 $1$
• $3 \to 2$ 长度 $1$
• $3 \to 1$ 长度 $10$
• $4 \to 5$ 长度 $2$
• $5 \to 2$ 长度 $7$（有两条相同道路）

从 $4$ 到 $1$：

• 最短路：$4 \to 5 \to 2 \to 3 \to 1$，长度 $2+7+1+10=20$
• 次短路：$4 \to 5 \to 2 \to 3 \to 2 \to 3 \to 1$，长度 $2+7+1+1+1+10=22$（中间可以循环） 需要统计所有长度为 $20$ 和 $21$ 的路径数量。

经过计算，共有 $2$ 条符合条件（样例输出）。

数据范围

• $2 \leq N \leq 1000$
• $1 \leq M \leq 10000$
• $1 \leq L \leq 1000$
• $1 \leq A,B,S,F \leq N$
• $T$ 组测试数据，$T$ 未给出但保证合理

时空限制

• 时间限制：1 秒
• 空间限制：64 MB