#include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 #define MP(a,b) make_pair(a,b)

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 const int INF = ( << ) - ;

 const int maxn = ;

 int path;

 int first1[maxn],nxt1[ * maxn],ecnt1;

 int first2[maxn],nxt2[ *maxn],ecnt2;

 int first[maxn],nxt[*maxn],ecnt;

 int dis1[maxn],dis2[maxn];

 int st,ed,lev[maxn],now[maxn];

 int n,m;

 int vis[*maxn];

 struct edge{

     int v,u,cost;

     int c;

     int next;

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

         return a.cost > b.cost;

     }

 };

 edge e1[*maxn],e2[*maxn],e[*maxn];

 void init(){

     ecnt1 = ecnt2 = ecnt = ;

     memset(first1,-,sizeof(first1));

     memset(first2,-,sizeof(first2));

     memset(first,-,sizeof(first));

 }

 void Add_edge1(int u,int v,int c){

     nxt1[++ecnt1] = first1[u];

     e1[ecnt1].u = u;

     e1[ecnt1].v = v;

     e1[ecnt1].cost = c;

     first1[u] = ecnt1;

 }

 void Add_edge2(int u,int v,int c){

     nxt2[++ecnt2] = first2[u];

     e2[ecnt2].v = v;

     e2[ecnt2].cost = c;

     first2[u] = ecnt2;

 }

 void Add_edge(int u,int v,int c){

     e[ecnt].next = first[u];

     e[ecnt].v = v;

     e[ecnt].u = u;

     e[ecnt].c = c;

     first[u] = ecnt++;

 }

 struct cmp{

     bool operator ()(pii a,pii b){

         return a.first > b.first;

     }

 };

 void Dijstra1(int s){

     priority_queue<pii,vector<pii >,cmp> PQ;

     dis1[s] = ;

     PQ.push(MP(dis1[s],s));

     int cnt = ;

     while(!PQ.empty()){

         pii x = PQ.top(); PQ.pop();

         if(dis1[x.second] < x.first) continue;

         for(int i = first1[x.second]; i != -; i = nxt1[i]){

             int v = e1[i].v;

             if(dis1[v] > dis1[x.second] + e1[i].cost){

                 dis1[v] = dis1[x.second] + e1[i].cost;

                 PQ.push(MP(dis1[v],v));

             }

         }

     }

 }

 void Dijstra2(int s){

     priority_queue<pii,vector<pii >,cmp> PQ;

     dis2[s] = ;

     PQ.push(MP(dis2[s],s));

     int cnt = ;

     while(!PQ.empty()){

         pii x = PQ.top(); PQ.pop();

         if(dis2[x.second] < x.first) continue;

         for(int i = first2[x.second]; i != -; i = nxt2[i]){

             int v = e2[i].v;

             if(dis2[v] > dis2[x.second] + e2[i].cost){

                 dis2[v] = dis2[x.second] + e2[i].cost;

                 PQ.push(MP(dis2[v],v));

             }

         }

     }

 }

 bool bfs(){

     queue<int> q;

     while(!q.empty()) q.pop();

     q.push(st);

     memset(lev,-,sizeof(lev));

     lev[st] = ;

     while(!q.empty()){

         int x = q.front();q.pop();

         for(int i = first[x];~i;i = e[i].next){

             int v = e[i].v;

             if(lev[v] <  && e[i].c > ){

                 lev[v] = lev[x] + ;

                 q.push(v);

             }

         }

     }

     return lev[ed] != -;

 }

 int dfs(int p,int minf){

     if(p == ed || minf == ) return minf;

     for(int &i = now[p];~i;i = e[i].next){

         int v = e[i].v;

         if(lev[v] == lev[p] +  && e[i].c > ){

             int d = dfs(v,min(e[i].c,minf));

             if(d > ){

                 e[i].c -= d;

                 e[i^].c += d;

                 return d;

             }

         }

     }

     return ;

 }

 int dinic(){

     int max_flow = ,p1;

     while(bfs()){

         memcpy(now,first,sizeof(first));

         while((p1 = dfs(st,INF)) > )

         max_flow += p1;

     }

     return max_flow;

 }

 int main(){

     int a,b,c;

     int T;

     scanf("%d",&T);

     while(T--){

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

         init();

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

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

             Add_edge1(a,b,c);

             Add_edge2(b,a,c);

         }

         scanf("%d %d",&st,&ed);

         for(int i = ;i <= n;i++) dis1[i] = dis2[i] = INF;

         Dijstra1(st);

         Dijstra2(ed);

         path = dis1[ed];

      //   for(int i = 1;i <= n;i++)

       //  printf("dis1[%d] = %d  dis2[%d] = %d\n",i,dis1[i],i,dis2[i]);

         for(int u = ;u <= n;u++){

             for(int i = first1[u];~i;i = nxt1[i]){

                 int v = e1[i].v;

                 if(dis1[u] + dis2[v] +e1[i].cost == path){

                 //    printf("u = %d  v = %d\n",u,v);

                     Add_edge(u,v,);

                     Add_edge(v,u,);

                 }

             }

         }

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

     }

     return ;

 }