/*对dij的再一次理解每个点依旧永久标记只不过这里多搞一维  0 1 表示最短路还是次短路然后更新次数相当于原来的两倍更新的时候搞一下就好了*/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector>#define maxn 1010using namespace std;int T,n,m,num,head[maxn],dis[maxn][2],f[maxn][2],c[maxn][2];struct edge{    int v,t,pre;}e[maxn*10];struct node{    int k,r,t;    bool operator < (const node &x) const{        return t>x.t;    }};priority_queue<node>q;int init(){    int x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}void Clear(){    for(int i=1;i<=n;i++)        head[i]=0;    num=0;    while(!q.empty())q.pop();}void Add(int from,int to,int dis){    num++;e[num].v=to;    e[num].t=dis;    e[num].pre=head[from];    head[from]=num;}void Dij(int u,int v){    memset(dis,127/3,sizeof(dis));    memset(f,0,sizeof(f));    memset(c,0,sizeof(c));    c[u][0]=1;    dis[u][0]=0;    q.push((node){u,0,0});    while(!q.empty()){        int k=q.top().k;int r=q.top().r;        q.pop();if(f[k][r])continue;        f[k][r]=1;        for(int i=head[k];i;i=e[i].pre){            int v=e[i].v;            if(dis[v][0]>dis[k][r]+e[i].t){                dis[v][1]=dis[v][0];                c[v][1]=c[v][0];                dis[v][0]=dis[k][r]+e[i].t;                c[v][0]=c[k][r];                q.push((node){v,0,dis[v][0]});                q.push((node){v,1,dis[v][1]});            }            else if(dis[v][0]==dis[k][r]+e[i].t){                c[v][0]+=c[k][r];                q.push((node){v,0,dis[v][0]});            }             else if(dis[v][1]>dis[k][r]+e[i].t){                dis[v][1]=dis[k][r]+e[i].t;                c[v][1]=c[k][r];                q.push((node){v,1,dis[v][1]});            }            else if(dis[v][1]==dis[k][r]+e[i].t){                c[v][1]+=c[k][r];                q.push((node){v,1,dis[v][1]});            }        }    }    int ans=c[v][0];    if(dis[v][1]==dis[v][0]+1)ans+=c[v][1];    printf("%d\n",ans);}int main(){    T=init();    while(T--){        n=init();m=init();        int u,v,t;Clear();        for(int i=1;i<=m;i++){            u=init();v=init();t=init();            Add(u,v,t);        }        u=init();v=init();        Dij(u,v);    }    return 0;}