#include <bits/stdc++.h>

 #define MAXN 1010

 using namespace std;

 vector<pair<int, int> > mp[MAXN]; //***记录图

 int dist[MAXN][]; //***记录源点此时到 i 的距离状态即最短路距离和次短路距离

 int cnt[MAXN][]; //***记录该点作为最短路节点和次短路节点入队次数

 int vis[MAXN][]; //***标记该点的状态即在最短路中，在次短路中，或者未被标记

 const int inf=0x3f3f3f3f;

 struct node{ //***重载比较符使优先队列非升序排列

     int point, value, tag;//***point记录点, value记录源点到此点的距离，tag标记次点是在最短路中或者在次短路中

     friend bool operator< (node a, node b){

         return  a.value!=b.value? a.value>b.value : a.point>b.point;

     }

 };

 int dijkstra_heap_k(int s){

     priority_queue<node> q;

     memset(dist, 0x3f, sizeof(dist));

     memset(vis, false, sizeof(vis));

     memset(cnt, , sizeof(cnt));

     dist[s][]=;

     cnt[s][]=;

     q.push({s, , });

     while(!q.empty()){

         node u=q.top();

         int point=u.point;

         int tag=u.tag;

         q.pop();

         if(vis[point][tag]){

             continue;

         }else{

             vis[point][tag]=;

         }

         for(int i=; i<mp[point].size(); i++){

             int v=mp[point][i].first;

             int cost=mp[point][i].second;

             //***找到比当前最短路更优的路径

             if(!vis[v][]&&dist[v][]>u.value+cost){

                 // 将之前的最短路变为次短路

                 if(dist[v][]!=inf){

                     dist[v][]=dist[v][];

                     cnt[v][]=cnt[v][];

                     q.push({v, dist[v][], });

                 }

                 //***更新最短路

                 dist[v][]=u.value+cost;

                 cnt[v][]=cnt[point][tag];

                 q.push({v, dist[v][], });

             }else if(!vis[v][]&&dist[v][]==u.value+cost){

                 //***找到一条和当前最短路距离一样的路径，更新最短路数目

                 cnt[v][]+=cnt[point][tag];

             }else if(!vis[v][]&&dist[v][]>u.value+cost){

                 // 比最短路长，比当前次短路短

                 dist[v][]=u.value+cost;

                 cnt[v][]=cnt[point][tag];

                 q.push({v, dist[v][], });

             }else if(!vis[v][]&&dist[v][]==u.value+cost){

                 // 和当前次短路一样长

                 cnt[v][]+=cnt[point][tag];

             }

         }

     }

 }

 int main(void){

     ios::sync_with_stdio(false), cin.tie(), cout.tie();

     int t, n, m;

     cin >> t;

     while(t--){

         cin >> n >> m;

         while(m--){

             int x, y, z;

             cin >> x >> y >> z;

             mp[x].push_back({y, z}); //**记录有向图

         }

         int s, e;

         cin >> s >> e;

         dijkstra_heap_k(s);

         if(dist[e][]+==dist[e][]){

             cout << cnt[e][]+cnt[e][] << endl;

         }else{

             cout << cnt[e][] << endl;

         }

         for(int i=; i<MAXN; i++){

             mp[i].clear();

         }

     }

     return ;

 }