题目翻译：观光路线规划

描述

旅游公司$Your Personal Holiday$组织比荷卢地区的巴士观光旅行。每天巴士从城市S出发前往城市F。途中，游客可以欣赏路线沿途的景点，巴士还会在一些美丽的城市停留（零个或多个）。

不同游客群体可能对想参观的景点有不同偏好，因此需要不同的从$S$到$F$的路线。为此，公司希望为客户提供多种路线选择。不过，由于酒店已提前预订，起点$S$和终点$F$是固定的。两条路线被视为不同，当且仅当至少存在一条从城市$A$到城市$B$的道路属于其中一条路线但不属于另一条。

路线选择有一个限制：为了给观光和节省燃油留出足够时间，巴士必须选择最短路线或比最短路线长$1$个单位的路线。通过允许长$1$个单位的路线，游客可以有更多选择，提升个性化体验。

例如，在下图的路线图中，从S=1到F=5的最短路线有两条：$1→2→5$和$1→3→5$，长度均为$6$。长$1$个单位的路线有一条：$1→3→4→5$，长度为$7$。

输入

输入第一行包含一个整数：测试用例数量。每个测试用例格式如下：

• 第一行：两个整数$N$和$M（2≤N≤1000，1≤M≤10000）$，表示城市数和道路数。
• 接下来$M$行，每行三个整数$A、B、L（1≤A,B≤N，A≠B，1≤L≤1000）$，表示从$A$到$B$的单向道路，长度为$L$。可能存在多条同起点和终点的道路。
• 最后一行：两个整数$S$和$F（1≤S,F≤N，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

提示

第一个测试用例对应题目描述中的示例图。

来源

BAPC 2006 资格赛