#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b ,int c){
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}
int cnt[N][2], dis[N][2]; // 图论 -> dp
bool vis[N][2];
int n, m, st, ed;
struct node{
    int ver, type, dist;
    bool operator < (const node& d) const {
        return dist>d.dist;
    }
};
int dijkstra(int x){
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    priority_queue<node> pq;
    pq.push({x, 0, 0});
    dis[x][0]=0, cnt[x][0]=1; // 初始化
    while(pq.size()){
        auto tmp=pq.top(); pq.pop();
        int ver=tmp.ver, type=tmp.type, distance=tmp.dist, count=cnt[ver][type];

        if(vis[ver][type]) continue; // dijkstra 的套路，出队就锁住
        vis[ver][type]=true;

        for(auto i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(dis[j][0]>distance+w[i]){
                dis[j][1]=dis[j][0], cnt[j][1]=cnt[j][0];
                pq.push({j, 1, dis[j][1]}); // 重要：dis 更新就要重新入队
                dis[j][0]=distance+w[i], cnt[j][0]=count;
                pq.push({j, 0, dis[j][0]});
            }else if(dis[j][0]==distance+w[i]){
                cnt[j][0]+=count;
            }else if(dis[j][1]>distance+w[i]){
                dis[j][1]=distance+w[i], cnt[j][1]=count;
                pq.push({j, 1, dis[j][1]});
            }else if(dis[j][1]==distance+w[i]){
                cnt[j][1]+=count;
            }
        }
    }
    int ans=cnt[ed][0];
    if(dis[ed][0]+1==dis[ed][1]) ans+=cnt[ed][1];

    return ans;
}

int main(){
    int T; cin>>T;
    while(T--){
        memset(h, -1, sizeof h); idx=0; // 初始化
        cin>>n>>m;
        while(m--){
            int a, b, c;
            cin>>a>>b>>c;
            add(a, b, c);
        }
        cin>>st>>ed;
        cout<<dijkstra(st)<<endl;
    }

    return 0;
}