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