题目描述

最短路径条数统计已经难不倒你了。

那么再加上次短路径的条数统计呢？

N 个点，编号为 1 ~ N。M 条有向边。可能有自环，可能有重边。求 S 号点到 T 号点的最短路和次短路的总条数。

注：本题中的次短路指的是比最短路长度多 1 个单位长度的路径。本题中允许多次走同一条边。中途可以多次经过同一个点，包括终点也可以多次经过。

多组数据。

输入格式

第一行：一个整数 T，表示数据组数。

对于每组数据：

• 第一行：两个整数 N, M
• 接下来 M 行：每行三个整数 u, v, w，表示从 u 到 v 有一条长度为 w 的有向边。
• 接下来一行：两个整数 S, T，数据保证 S ≠ T，且 S 到 T 至少存在一条路径。

输出格式

每组数据的答案占一行。答案保证不超过 $10^9$。

输入样例

3
3 3
1 2 1
1 3 1
3 2 1
1 2
3 3
1 2 1
1 3 1
3 2 2
1 2
2 4
1 1 1
2 2 1
1 2 1
1 2 2
1 2

输出样例

2
1
4

数据范围

2≤N≤1000, 1≤M≤10000, 1≤u,v,S,T≤N, 1≤w≤1000