#include <bits/stdc++.h>
using namespace std;
struct AI{
	long long zhi,zhong;
};
struct node{
	long long hao,zhi;
	friend bool operator<(const node a,const node b)
    {
        return a.zhi>b.zhi;
    }
};
long long n,s,e,w,d[20010],t,ans=0;
vector <AI> a[20010];
bool f[20010],res[20010];
void dfs(int k,int z){
	if(z>d[e]+1){
		return;
	}
	if(k==e&&(z==d[e]||d[e]+1)){
		ans++;
	}
	else{
		for(int i=0;i<a[k].size();i++){
			if(res[a[k][i].zhong]==0){
				res[a[k][i].zhong]=1;
				dfs(a[k][i].zhong,z+a[k][i].zhi);
				res[a[k][i].zhong]=0;	
			}
		}
	}
}
priority_queue <node> q; 
int main(){
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	scanf("%d",&t);
	for(int ii=1;ii<=t;ii++){
		ans=0; 
		cin>>n>>w;
		for(long long i=1;i<=w;i++){
			long long r;
			cin>>r;
			long long o,x;
			cin>>o>>x;
			a[r].push_back({x,o});
		}
		cin>>s>>e;
		memset(d,0x7f,sizeof(d));
		memset(f,0,sizeof(f)); 
		long long h;
		d[s]=0;
		q.push({s,d[s]});
		while(!q.empty()) {
			h=q.top().hao;
			q.pop();
			if(f[h]){
				continue;
			}
			f[h]=true;
			if(h==e){
				break;
			}
			for(long long j=0;j<a[h].size();j++){
				if(d[a[h][j].zhong]>d[h]+a[h][j].zhi){
					d[a[h][j].zhong]=d[h]+a[h][j].zhi;
					q.push({a[h][j].zhong,d[a[h][j].zhong]});
				}
			}
		}
		dfs(s,0);
		cout<<ans<<endl;
		for(int i=1;i<=n;i++){
			a[i].clear();
		}
		while(!q.empty()){
			q.pop();
		} 
	}
	return 0;
}