题目描述

给定一张包含$n$个点、$m$条边的有向图，并且给定起始点$s$和终点$t$，求从$s$到$t$的最短路线和比最短路线多一个单位距离的路线的总方案数。（两条路线$A、B$不同当且仅当存在一条边 $∈A$且$∉B$）。

输入

输入包含多组数据。 第一行包含一个整数$T$表示测试数据的个数。对于每组测试数据： 第一行包含两个整数$n,m$，分别表示图中点的数量和边的数量。 接下来$m$行，每行包含$3$个整数$x,y,w$，表示有一条从$x$连向$y$的（$x≠y$）权值为$w$的单向边。 最后一行包含两个整数$s,t$，数据保证$s≠t$且至少有一条从$s$到$t$的路线。

输出

对于每组数据，输出一个整数表示总方案数，保证所有数据都在$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

提示

【数据规模及约定】 对于100%的数据，满足$2≤n≤1000，1≤m≤10000，1≤x,y,s,t≤n，1≤c≤1000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。