Description

中文标题：观光旅游

旅游运营商 Your Personal Holiday 组织比荷卢经济联盟的导游巴士旅行。每天，巴士都会从一个城市 $S$ 行驶到另一个城市 $F$。在这条路上，巴士上的游客可以看到沿途的景点。此外，公共汽车在一些美丽的城市停靠了几站（零站或更多站），游客们可以在那里下车欣赏当地的风景。

不同的游客群体可能对他们想看的景点有不同的偏好，因此对从 $S$ 到 $F$ 的路线也有不同的喜好。因此，Your Personal Holiday 希望为客户提供许多不同路线的选择。由于酒店已提前预订，出发城市 $S$ 和最终城市 $F$ 是固定的。如果从城市 $A$ 到城市 $B$ 至少有一条道路是一条路线的一部分，而不是另一条路线，则认为从 $S$ 到 $F$ 的两条路线是不同的。

游客可以选择的路线有限制。为了在车站有足够的时间观光（并避免使用过多的燃料），公共汽车必须从 $S$ 到 $F$ 走一条短途路线。它必须是一条距离最小的路线，或者是一条比最小距离长一个距离单位的路线。事实上，通过允许延长一个距离单位的路线，游客可能比将他们限制在最短的路线上有更多的选择。这增强了个人假期的印象。

例如，对于上述路线图，从 $S=1$ 到 $F=5$ 有两条最小路线：$1→2→5$ 和 $1→3→5$，长度均为 $6$ 。有一条路线长一个距离单位：$1→3→4→5$，长度为 $7$。

现在，给定比荷卢经济联盟和两个城市 $S$ 和 $F$ 的部分路线图，旅游运营商 Your Personal Holiday 想知道在上述路线长度限制下，它可以为客户提供多少条不同的路线。

Input Format

输入文件的第一行包含一个数字：要遵循的测试用例的数量。每个测试用例都有以下格式：

• 一条由两个整数 $N$ 和 $M$ 组成的线，用一个空格隔开，$2≤N≤1000$，$1≤M≤10000$：路线图中的城市数量和道路数量。

• $M$ 条线，每条线有三个整数 $A$、$B$ 和 $L$，由单个空格分隔，$1≤A,B≤N$，$A \ne B$，$1≤L≤1000$，描述了一条从 $A$ 市到 $B$ 市的长度为 $L$ 的道路。这些道路是单向的。因此，如果有一条从 $A$ 到 $B$ 的路，那么从 $B$ 到 $A$ 就不一定也有路。从 $A$ 市到 $B$ 市可能有不同的路。

• 一条有两个整数 $S$ 和 $F$ 的线，用一个空格隔开，$1≤S,F≤N$，$S \ne F$ ：路线的起点城市和终点城市。从 $S$ 到 $F$ 至少有一条路线。

Output Format

对于输入文件中的每个测试用例，输出应该在一行上包含一个数字：最小长度或更长一个距离单位的路由数量。测试用例是这样的，这个数字最多为 $10^9=1000000000$。

翻译提供者：csyc5586

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