不需要跑次短路，用通法来解决这个题。
通法题：逛公园

（而且这题没有毒瘤的0环，容易多了）

先跑一遍最短路把到每个点的最短距离$dis[u]$求出来。
然后dp：设当前考虑的点是u,到这个点的距离是$dis[u]+k$,$f[k][u]$表示到$u$,长度为$dis[u]+k$的路径数量
它会对$dis[v]=dis[u]+w(u,v)$的$v$产生$f[k][v]+=f[k][u]$的贡献；并且如果$k=0,dis[v]+1=dis[u]+w(u,v)$还会产生$f[1][v]+=f[0][u]$的贡献
为了消除后效性，需要按照$dis[u]$排序再dp，最后的答案就是$f[0][t]+f[1][t]$

时间复杂度瓶颈在于最短路，为$O(mlogn)$

/**********/
#define MAXN 2011
#define MAXM 20011
struct Edge
{
    ll v,w,nxt;
}e[MAXM];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
    ++cnt;
    e[cnt].v=v;e[cnt].w=w;
    e[cnt].nxt=last[u],last[u]=cnt;
}

ll dis[MAXN];
struct node
{
    ll u,dis;
    node(ll _u=0,ll _dis=0)
    {
        u=_u,dis=_dis;
    }
    bool operator <(const node& t)
    const
    {
        return dis>t.dis;
    }
};
std::priority_queue<node>q;
void Dij(ll s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push(node(s,0));
    while(!q.empty())
    {
        ll u=q.top().u,tmp=q.top().dis;q.pop();
        if(dis[u]!=tmp)continue;
        for(ll i=last[u];i;i=e[i].nxt)
        {
            ll v=e[i].v;
            if(umin(dis[v],dis[u]+e[i].w))q.push(node(v,dis[v]));
        }
    }
}
ll f[2][MAXN],ord[MAXN];
bool cmp(ll x,ll y)
{
    return dis[x]<dis[y];
}
void work()
{
    cnt=0;memset(last,0,sizeof last);
    memset(f,0,sizeof f);
    ll n=read(),m=read();
    for(ll i=1;i<=m;++i)
    {
        ll u=read(),v=read(),w=read();
        adde(u,v,w);
    }
    ll s=read(),t=read();
    Dij(s);
    for(ll i=1;i<=n;++i)ord[i]=i;
    std::sort(ord+1,ord+n+1,cmp);
    f[0][s]=1;
    for(ll k=0;k<=1;++k)
        for(ll p=1;p<=n;++p)
        {
            ll u=ord[p];
            //printf("dis[%lld]=%lld\n",u,dis[u]);
            for(ll i=last[u];i;i=e[i].nxt)
            {
                ll v=e[i].v;
                if(dis[u]+e[i].w==dis[v])f[k][v]+=f[k][u];
                if(k==0&&dis[u]+e[i].w==dis[v]+1)f[1][v]+=f[0][u];
            }
        }
    printf("%lld\n",f[0][t]+f[1][t]);
}
int main()
{
    ll task=read();
    while(task--)work();
    return 0;
}