#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5, M = 1e4 + 5;
struct Ver {
	int ver, type, dist;
	bool operator > (const Ver& W) const {
		return dist > W.dist;
	}
};
int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
int vis[N][2];
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int Dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	memset(cnt, 0, sizeof cnt);
	priority_queue<Ver, vector<Ver>, greater<Ver> >heap;
	dist[S][0] = 0, cnt[S][0] = 1;
	heap.push({ S,0,0 });
	while (!heap.empty()) {
		Ver t = heap.top();
		heap.pop();
		int ver = t.ver, type = t.type, d = t.dist, count = cnt[ver][type];
		if (vis[ver][type])continue;
		vis[ver][type] = 1;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j][0] > d + w[i]) {
				dist[j][1] = dist[j][0];
				cnt[j][1] = cnt[j][0];
				heap.push({ j,1,dist[j][1] });
				dist[j][0] = d + w[i];
				cnt[j][0] = count;
				heap.push({ j,0,dist[j][0] });
			}
			else if (dist[j][0] == d + w[i]) {
				cnt[j][0] += count;
			}
			else if (dist[j][1] > d + w[i]) {
				dist[j][1] = d + w[i];
				cnt[j][1] = count;
				heap.push({ j,1,dist[j][1] });
			}
			else if(dist[j][1] == d + w[i]) {
				cnt[j][1] += count;
			}
		}
	}
	int ret = cnt[T][0];
	if (dist[T][1] == dist[T][0] + 1)ret += cnt[T][1];
	return ret;
}
int main() {
		freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int TT;
	cin >> TT;
	while (TT--) {
		memset(h, -1, sizeof h);
		memset(vis, 0, sizeof vis);
		idx = 0;
		cin>>n>>m; 
		for (int i = 1, a, b, c; i <= m; i++) {
			cin>>a>>b>>c;
			add(a, b, c);
		}
		cin>>S>>T;
		cout<<Dijkstra()<<endl;
	}
	return 0;
}