// 最短路 Dijkstra 算法 O(mlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=1010,M=10010;
int h[N],to[M],w[M],ne[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
struct P{
  int p,t,d; //点，类型，距离
  bool operator<(const P &b)const{
    return d>b.d;
  }
};
int n,m,S,T;
int d[N][2],cnt[N][2];
bool vis[N][2];

int dijkstra(){
  memset(vis,0,sizeof vis);
  memset(d,0x3f,sizeof d); d[S][0]=0;
  memset(cnt,0,sizeof cnt); cnt[S][0]=1;
  priority_queue<P> q;
  q.push({S,0,0});
  while(!q.empty()){
    auto[u,t,du]=q.top(); q.pop();
    if(vis[u][t]) continue;
    vis[u][t]=1;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i];
      if(d[v][0]>du+w[i]){ //找到更短的最短路
        d[v][1]=d[v][0];   //更新次短路
        cnt[v][1]=cnt[v][0];
        q.push({v,1,d[v][1]});
        d[v][0]=du+w[i];   //更新最短路
        cnt[v][0]=cnt[u][t];
        q.push({v,0,d[v][0]});
      }
      else if(d[v][0]==du+w[i]){ //找到等长的最短路
        cnt[v][0]+=cnt[u][t];
      }
      else if(d[v][1]>du+w[i]){ //找到更短的次短路
        d[v][1]=du+w[i];        //更新次短路
        cnt[v][1]=cnt[u][t];
        q.push({v,1,d[v][1]});
      }
      else if(d[v][1]==du+w[i]){ //找到等长的次短路
        cnt[v][1]+=cnt[u][t];
      }
    }
  }
  return cnt[T][0]+(d[T][0]+1==d[T][1])*cnt[T][1];
}
int main(){
  int t; scanf("%d",&t);
  while(t--){
    idx=0; memset(h,0,sizeof h);
    scanf("%d%d",&n,&m);
    for(int a,b,c;m--;){
      scanf("%d%d%d",&a,&b,&c);
      add(a,b,c);
    }
    scanf("%d%d",&S,&T);
    printf("%d\n",dijkstra());
  }
}

#include<bits/stdc++.h>
using namespace std;
struct edge{int x,y,c,pre;}a[21100];int alen,last[21100];
void ins(int x,int y,int c){a[++alen]=edge{x,y,c,last[x]};last[x]=alen;}
int n,m,st,ed,d[1100];bool v[1100];
void spfa()
{
    memset(v,0,sizeof(v));v[st]=1;
    memset(d,0x0f,sizeof(d));d[st]=0;
    queue<int>q;q.push(st);
    while(!q.empty())
    {
        int x=q.front();q.pop();v[x]=0;
        for(int k=last[x];k;k=a[k].pre)
        {
            int y=a[k].y;
            if(d[y]>d[x]+a[k].c)
            {
                d[y]=d[x]+a[k].c;
                if(!v[y])q.push(y);v[y]=1;
            }
        }
    }
}
int ans,md;
void dfs(int x,int s)
{
    if(s>md) return;
    v[x]=1;
    for(int k=last[x];k;k=a[k].pre)
    {
        int y=a[k].y;
        if(!v[y])
        {
            if(y==ed&&s+a[k].c<=md) 
            {
                ans++;
                continue;
            }
            dfs(y,s+a[k].c);
            v[y]=0;
        }
    }
    v[x]=0;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        alen=0;memset(last,0,sizeof(last));
        for(int i=1;i<=m;i++)
        {
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            ins(x,y,c);
        }
        scanf("%d%d",&st,&ed);
        spfa();md=d[ed]+1;
        
        ans=0;
		memset(v,0,sizeof(v));
        dfs(st,0);
        
        printf("%d\n",ans);
    }
    return 0;
}