#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
int N, M;
struct edge { int v, c; };
vector<edge> G[maxn];
int S, F;

struct Dij
{
    int u, c, flog;
    bool operator< (const Dij& r) const
    {
        return c>r.c;
    }
};

int dist[maxn][2], vis[maxn][2], dp[maxn][2];
void dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    memset(dp, 0, sizeof(dp));
    dp[S][0]=1; dist[S][0]=0;
    priority_queue<Dij> que;
    que.push((Dij){S, 0, 0});
    while(!que.empty())
    {
        Dij tp = que.top(); que.pop();
        int u = tp.u, flog = tp.flog;    //使用这个状态更新其他的
        if(vis[u][flog]) continue;
        vis[u][flog] = 1;
        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i].v, c = G[u][i].c;
            int w = dist[u][flog] + c;
            if(w < dist[v][0])    //更新次短路 最短路

            {
                if(dist[v][0] != inf)
                {
                    dist[v][1] = dist[v][0];
                    dp[v][1] = dp[v][0];
                    que.push((Dij){v, dist[v][1], 1});
                }
                dist[v][0] = w;
                dp[v][0] = dp[u][flog];
                que.push((Dij){v, dist[v][0], 0});
            }
            else if(w == dist[v][0])      //更新方法数
                dp[v][0] += dp[u][flog];
            else if(w < dist[v][1])   //更新次短路
            {
                dist[v][1] = w;
                dp[v][1] = dp[u][flog];
                que.push((Dij){v, dist[v][1], 1});
            }
            else if(w == dist[v][1])    //更新方法数
                dp[v][1] += dp[u][flog];
        }
    }
}

int main()
{
	freopen("sightseeing.in","r",stdin);
	freopen("sightseeing.out","w",stdout);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &M);
        for(int i=0; i<=N; i++) G[i].clear();
        for(int i=0; i<M; i++)
        {
            int u, v, t;
            scanf("%d%d%d", &u, &v, &t);
            G[u].push_back((edge){v, t});
            //G[v].push_back((edge){u, t});
        }
        scanf("%d%d", &S, &F);
        dijkstra();
        if(dist[F][1]-dist[F][0] == 1)
            printf("%d\n", dp[F][0]+dp[F][1]);
        else
            printf("%d\n", dp[F][0]);
    }
    return 0;
}