Sightseeing

Tour operator Your Personal Holiday runs guided bus trips across the Benelux. Every day the bus drives from one city S to another city F. On the way the passengers watch the sights beside the road, and the bus also stops in a few beautiful cities (possibly none), where the passengers get out to see the local sights.

Different groups of tourists want to see different sights, so they prefer different routes from S to F. Your Personal Holiday therefore wants to offer its clients a choice of many routes. The hotels are booked in advance, so the starting city S and the final city F are fixed. Two routes from S to F count as different if at least one road from a city A to a city B belongs to one route but not to the other.

There is one restriction on the routes the tourists may choose from. To leave enough time for sightseeing at the stops and to save fuel, the bus has to take a short route from S to F. The length of the route has to be the minimal distance, or exactly one distance unit more than the minimal distance. Allowing routes that are one unit longer gives the tourists more choice than the minimal routes alone.

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

Given a (partial) road map of the Benelux and two cities S and F, count the different routes that Your Personal Holiday can offer under this restriction on the route length.

The first line contains the number of test cases. Each test case has the following format.

• One line with two integers $N$ and $M$, separated by a single space: the number of cities and the number of roads. ($2 \le N \le 1000$, $1 \le M \le 10000$)
• $M$ lines, each with three integers $A$, $B$ and $L$, separated by single spaces, describing a road from city $A$ to city $B$ of length $L$. ($1 \le A, B \le N$, $A \ne B$, $1 \le L \le 1000$)
• One line with two integers $S$ and $F$, separated by a single space: the starting city and the final city of the route. ($1 \le S, F \le N$, $S \ne F$)

The roads are one way. If there is a road from $A$ to $B$, there is not necessarily also a road from $B$ to $A$. There may be several different roads from a city $A$ to a city $B$.

At least one route from $S$ to $F$ exists.

For every test case print one line with a single number: the number of routes whose length is the minimal distance or exactly one distance unit more. The test data guarantee that this number is at most $10^9$.

The picture in the problem statement is the map of the first of the two test cases in the first example.