#include <bits/stdc++.h>
#define pii pair <int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
int t,n,m,num[10010],s,f,res;
int mk[10010],dis[10010];
int head[10010],tot;
struct edge {
	int v,w,nxt;
}e[100010];
void add (int u,int v,int w) {
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void dijkstra (int s) {
	for (int i=1;i<=1005;i++) dis[i]=1e9;
	priority_queue<pii>q;
	q.push(mp(0,s));
	dis[s]=0;
	while (!q.empty()) {
		int u=q.top().se;
		q.pop();
		if (mk[u]) continue;
		mk[u]=1;
		for (int i=head[u];i;i=e[i].nxt) {
			int v=e[i].v,w=e[i].w;
			if (dis[v]>dis[u]+e[i].w) {
				dis[v]=dis[u]+e[i].w;
				q.push(mp(-dis[v],v));
			}
		}
	}
	return;
}
void dfs (int u,int sum) {
	if (sum>dis[f]+1) {
		return;
	}
	if (u==f) {
		if (sum==dis[f]||sum==dis[f]+1) {
			res++;
		}
	}
	for (int i=head[u];i;i=e[i].nxt) {
		int v=e[i].v;
		if (mk[v]) continue;
		mk[v]=1;
		dfs(v,sum+e[i].w);
		mk[v]=0;
	}
	return;
}
int main () {
    freopen("sightseeing.in","r",stdin);
    freopen("sightseeing.out","w",stdout);
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i=1;i<=n;i++) head[i]=0,mk[i]=0;
		tot=res=0;
		for (int i=1;i<=m;i++) {
			int a,b,c;
			cin >> a >> b >> c;
			add(a,b,c);
		}
		cin >> s >> f;
		dijkstra(s);
		//cout << dis[f] <<endl;
		for (int i=1;i<=n;i++) mk[i]=0;
		dfs(s,0);
		cout << res <<endl;
	}
	return 0;
}