3227. [POJ 3463] 观光

以该地图为例，从城市$S$到城市$F$($S = 1, F = 5$)的最短路径有两条,分别为$ 1 → 2 → 5 $和$ 1 → 3 → 5 $，其长度均为$ 6 $。还有一条长度比最短路线长一个单位距离的路线，为$ 1 → 3 → 4 → 5 $，其长度为$ 7 $。现在，有好几张比荷卢三国的(部分)地图，起点城市$S$和终点城市$F$。$Your$ $Personal$ $Holiday$ 旅行社想知道按照以上路线选择方法，有多少种不同的路线可以提供给游客们。

【输入格式】

每个输入文件包含多组数据。

输入文件的第一行,包含一个正整数$T$,代表该输入文件中所含的数据组数。

接下来是$T$组数据,每组数据的格式如下：

第一行包含两个整数$N$和$M$,两个数之间以一个空格分开，分别代表城市的数量和地图上道路的个数。

接下来的$M$行,每行包含三个整数$A$、$B$和$L$,每个数之间以一个空格分开,代表从$A$城市到达$B$城市的路径长度为$L$.这些道路是单向的。因此，如果有从城市$A$到城市$B$的道路，但不一定有从城市$B$到城市$A$的道路,但不排除测试数据中提供双向道路的情况。

第 $M+2$ 行包含两个整数$S$和$F$，两个数之间以一个空格分开，代表本次观光游览的起点城市与终点城市。

保证存在至少一条可以从城市$S$到达城市$F$的路线。

【输出格式】

输出文件包含$T$行，分别对应$T$组数据的答案，每组数据的答案格式如下：

一个整数，表示最短路径和长度比最短路径长 $1$ 单位路径的路径的数量和。

【样例输入】

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

【提示】

第一个测试数据对应着题目描述中的图片。由于输入量较大，建议使用$sacnf()$代替$C++$中的$cin$;

对于加强后的数据，测试点满足以下性质:

对于 $100\%$ 的数据，保证有：

$2≤N≤1×10^3, 1≤M≤1×10^4, 1≤A,B≤N, A≠B, 1≤L≤1×10^3, 1≤S,F≤N, S≠F, T≤300.$

【来源】

PKU JudgeOnline T3463 大样例