#include<bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
using namespace std;
int t,n,m,num[10010],s,f,ans,vis[10010],dis[10010];
int head[10010],cnt;
struct edge{
	int v,w,nxt;
}e[100010];
void addedge(int u,int v,int w) {
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dijkstra(int s){
	priority_queue<pii>q;
	q.push(make_pair(0,s));
	dis[s]=0;
	while (!q.empty()) {
		int u=q.top().se; q.pop();
		if(vis[u]) continue; vis[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(make_pair(-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) ans++;
	}
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].v;
		if(vis[v]) continue;
		vis[v]=1;
		dfs(v,sum+e[i].w);
		vis[v]=0;
	}
}
int main(){
    freopen("sightseeing.in","r",stdin);
    freopen("sightseeing.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		memset(head,0,sizeof(head));
		memset(vis,0,sizeof(vis));
		ans=cnt=0;
		for(int i=1;i<=m;i++){
			int a,b,c; scanf("%d%d%d",&a,&b,&c);
			addedge(a,b,c);
		}
		scanf("%d%d",&s,&f);
		memset(dis,0x3f3f3f3f,sizeof(dis));
		dijkstra(s);
		memset(vis,0,sizeof(vis));
		dfs(s,0);
		printf("%d\n",ans);
	}
	return 0;
}