题目描述

Tour operator Your Personal Holiday organises guided bus trips across the Benelux. Every day the bus moves from one city S to another city F. On this way, the tourists in the bus can see the sights alongside the route travelled. Moreover, the bus makes a number of stops (zero or more) at some beautiful cities, where the tourists get out to see the local sights.

Different groups of tourists may have different preferences for the sights they want to see, and thus for the route to be taken from S to F. Therefore, Your Personal Holiday wants to offer its clients a choice from many different routes. As hotels have been booked in advance, the starting city S and the final city F, though, are fixed. Two routes from S to F are considered different if there is at least one road from a city A to a city B which is part of one route, but not of the other route.

There is a restriction on the routes that the tourists may choose from. To leave enough time for the sightseeing at the stops (and to avoid using too much fuel), the bus has to take a short route from S to F. It has to be either a route with minimal distance, or a route which is one distance unit longer than the minimal distance. Indeed, by allowing routes that are one distance unit longer, the tourists may have more choice than by restricting them to exactly the minimal routes. This enhances the impression of a personal holiday.

For example, for the above road map, there are two minimal routes from S = 1 to F = 5: 1 → 2 → 5 and 1 → 3 → 5, both of length 6. There is one route that is one distance unit longer: 1 → 3 → 4 → 5, of length 7.

Now, given a (partial) road map of the Benelux and two cities S and F, tour operator Your Personal Holiday likes to know how many different routes it can offer to its clients, under the above restriction on the route length.

输入格式

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with two integers N and M, separated by a single space, with 2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000: the number of cities and the number of roads in the road map.

• M lines, each with three integers A, B and L, separated by single spaces, with 1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000, describing a road from city A to city B with length L.The roads are unidirectional. Hence, if there is a road from A to B, then there is not necessarily also a road from B to A. There may be different roads from a city A to a city B.

• One line with two integers S and F, separated by a single space, with 1 ≤ S, F ≤ N and S ≠ F: the starting city and the final city of the route. There will be at least one route from S to F.

输出格式

For every test case in the input file, the output should contain a single number, on a single line: the number of routes of minimal length or one distance unit longer. Test cases are such, that this number is at most 109 = 1,000,000,000.

题目大意

中文标题：观光旅游

题目描述

旅游运营商 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 想知道在上述路线长度限制下，它可以为客户提供多少条不同的路线。

输入格式

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

• 一条由两个整数 $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$ 至少有一条路线。

输出格式

对于输入文件中的每个测试用例，输出应该在一行上包含一个数字：最小长度或更长一个距离单位的路由数量。测试用例是这样的，这个数字最多为 $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