#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define M 20005
int ver[M],val[M],Next[M],head[N],idx,ans[N],dis[N],d[N],vv[N],t,m,n,u,v,w,from[M],s,f;
void add(int u,int v,int w){
	from[++idx] = u;
	ver[idx] = v;
	val[idx] = w;
	Next[idx] = head[u];
	head[u] = idx;
}
void dij(int s){
	for(int i = 1; i <= n; i++){
		dis[i] = 1e9,vv[i] = 0,d[i] = 0;
	}
	queue<pair<int,int > >q;
	q.push(make_pair(s,0));
	dis[s] = 0;
	d[s] = 1;
	vv[s] = 1;
	while(q.size()){
		int now = q.front().first;
		q.pop();
		vv[now] = 0;
		for(int i = head[now] ; i ; i = Next[i]){
			int y = ver[i];
			if(dis[y] > dis[now]+val[i]){
				dis[y] = dis[now]+val[i];
				d[y] = d[now];
				if(!vv[y]){
					q.push(make_pair(y,-dis[y]));
					vv[y] = 1;
				}
			}else if(dis[y] == dis[now]+val[i]){
				d[y] += d[now];
			}
		}
	}
}
int main(){
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		idx = 0;
		scanf("%d%d",&n,&m);
		for(int i = 1; i <= m; i++){
			scanf("%d%d%d",&u,&v,&w);
			if(u == v) continue;
			add(u,v,w);
		}
		scanf("%d%d",&s,&f);
		dij(s);
		int ans = d[f];
		
		//for(int i = 1; i <= n; i++) cout << d[i] << ' ';
		for(int i = 1; i <= m; i++){
			
			if(ver[i] == f && dis[from[i]]+val[i]-1 == dis[f]){
			//cout << from[i] << endl;
				ans += d[from[i]];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}