#include<stdio.h>

 #include<string.h>

 #include<queue>

 #define mem(a, b) memset(a, b, sizeof(a))

 const int inf = 0x3f3f3f3f;

 using namespace std;

 int n, m;

 int tot, head[];

 int dis[][], cnt[][];//dis数组记录最短路 0 和次短路 1 距离，cnt数组记录最短路 0 和次短路 1 条数

 int vis[][];

 struct Edge

 {

     int to, next;

     int w;

 }edge[];

 void add(int a, int b, int w)

 {

     edge[++ tot].to = b;

     edge[tot].w = w;

     edge[tot].next = head[a];

     head[a] = tot;

 }

 struct Node//优先队列优化结构体,id为点的序号, dis为源点到该点的距离 p区分属于最短路还是次短路

 {

     int id, dis, p;

     bool operator < (const Node &a)const

     {

         return dis > a.dis;

     }

 }no;

 void init()

 {

     mem(head, -), tot = ;

     mem(vis, );  //代表源点到该点的距离未被确定

 }

 void dij(int s, int t)

 {

     priority_queue<Node> Q;

     while(!Q.empty())

         Q.pop();

     for(int i = ; i <= n; i ++) //初始化

     {

         dis[][i] = dis[][i] = inf;

         cnt[][i] = cnt[][i] = ;

     }

     dis[][s] = ;

     cnt[][s] = ;//源点到自己的最短路条数为1

     no.p = , no.dis = , no.id = s;

     Q.push(no);

     while(!Q.empty())

     {

         Node a = Q.top();

         Q.pop();

         if(vis[a.p][a.id])

             continue; //该p状态下已经确定过就跳过

         vis[a.p][a.id] = ;

         for(int i = head[a.id]; i != -; i = edge[i].next)

         {

             int to = edge[i].to;

             if(dis[][to] > dis[a.p][a.id] + edge[i].w) //最短路可以更新（在0或1状态下找到一条更短的路）

             {

                 dis[][to] = dis[][to];  //原来的最短路成为次短路

                 dis[][to] = dis[a.p][a.id] + edge[i].w;

                 cnt[][to] = cnt[][to];//次短路条数继承为原来的最短路条数

                 cnt[][to] = cnt[a.p][a.id];

                 no.p = , no.dis = dis[][to], no.id = to;

                 Q.push(no);

                 no.p = , no.dis = dis[][to], no.id = to;

                 Q.push(no);

             }

             else if(dis[][to] == dis[a.p][a.id] + edge[i].w)//最短路长度一样 更新最短路条数即可

             {

                 cnt[][to] += cnt[a.p][a.id];

             }

             else if(dis[][to] > dis[a.p][a.id] + edge[i].w)//找到一条长度大于最短路但小于当前次短路的路径

             {//将这条路变成次短路

                 dis[][to] = dis[a.p][a.id] + edge[i].w;

                 cnt[][to] = cnt[a.p][a.id];

                 no.p = , no.dis = dis[][to], no.id = to;

                 Q.push(no);

             }

             else if(dis[][to] == dis[a.p][a.id] + edge[i].w)

             {

                 cnt[][to] += cnt[a.p][a.id];

             }

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T --)

     {

         init();

         scanf("%d%d", &n, &m);

         for(int i = ; i <= m; i ++)

         {

             int a, b, c;

             scanf("%d%d%d", &a, &b, &c);

             add(a, b, c);

         }

         int s, t;

         scanf("%d%d", &s, &t);

         dij(s, t);

         int ans = cnt[][t]; //ans代表最短路的条数

         if(dis[][t] +  == dis[][t])

             ans += cnt[][t];

         printf("%d\n", ans);

     }

     return ;

 }