#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return f*x;
}
ll T;
ll n,m,a,b,l,s,f,t;
ll load[10010];
struct lu
{
	ll to;
	ll v;
};
vector<lu> mm[10010];
bool vis[10010];
ll min1,min2;
void dfs(ll p,ll k)
{
	if(vis[p]) return ;
	if(p==f)
	{
		load[++t]=k;
		if(k<min1) min1=k;
		else if(k>min1&&k<min2) min2=k;
		return ;
	}
	for(ll i=0;i<mm[p].size();i++)
	{
		vis[p]=1;
		dfs(mm[p][i].to,k+mm[p][i].v);
		vis[p]=0;
	}
}
int main() 
{
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
	T=read();
	while(T--)
	{
		min1=0x7fffffff;
		min2=0x7fffffff;
		n=read();m=read();
		memset(load,0,sizeof(load));
		memset(vis,0,sizeof(vis));
		for(ll i=1;i<=m;i++)
		{
			for(ll j=0;j<mm[i].size();i++)
			{
				mm[i][j].to=0;
				mm[i][j].v=0;
			}
		}
		t=0;
		for(ll i=1;i<=m;i++)
		{
			a=read();b=read();l=read();
			mm[a].push_back((lu){b,l});
		}
		s=read();f=read();
		dfs(s,0);
		ll ans=0;
		for(ll i=1;i<=t;i++)
		{
			if(load[i]==min1||load[i]==min2) ans++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}