#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> 
using namespace std; 
int n,m,S,F,t,h[1010],v[10010],w[10010],ne[10010],tot,dis[1010][2],f[1010][2]; 
bool st[1010][2];
struct V{
    int ver,type,dis;
    bool operator > (const V&v)const  
    {
        return dis>v.dis;
    }
};
void add(int x,int y,int z)
{
    tot++;
    v[tot]=y;
    w[tot]=z;
    ne[tot]=h[x];
    h[x]=tot;
}
int dijkstra()
{
    memset(st,0,sizeof(st));
    memset(dis,0x3f,sizeof(dis));
    memset(f,0,sizeof(f));
    dis[S][0]=0;
    f[S][0]=1;
    priority_queue<V,vector<V>,greater<V>> q;
    q.push({S,0,0});
    while(q.size())
    {
        V t=q.top();
        q.pop();
        int u=t.ver,type=t.type,d=t.dis,cnt=f[u][type];
        if(st[u][type]) continue;
        st[u][type]=true;
        for(int i=h[u];i;i=ne[i])
        {
            int y=v[i];
            if(dis[y][0]>d+w[i])
            {
                dis[y][1]=dis[y][0];
                f[y][1]=f[y][0]; 
                q.push({y,1,dis[y][1]}); 
                dis[y][0]=d+w[i];
                f[y][0]=cnt; 
                q.push({y,0,dis[y][0]});
            }
            else if(dis[y][0]==d+w[i]) 
            {
                f[y][0]+=cnt; 
            }
            else if(dis[y][1]>d+w[i])
            {
                dis[y][1]=d+w[i];
                f[y][1]=cnt;
                q.push({y,1,dis[y][1]});
            }
            else if(dis[y][1]==d+w[i]) 
            {
                f[y][1]+=cnt;
            }
        }
    }
    int ans=f[F][0]; 
    if(dis[F][1]==dis[F][0]+1) ans+=f[F][1];
    return ans;
}
int main()
{
    freopen("sightseeing.in","r",stdin);
    freopen("sightseeing.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(h,-1,sizeof(h));
        tot=0;
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        scanf("%d%d",&S,&F);
        printf("%d\n",dijkstra());
    }
    return 0;
}