3
7 8
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
1 7

6 7
1 2 1
2 3 1
1 3 3
3 4 1
3 5 1
4 6 1
5 6 1
1 6

2 2
1 2 1
1 2 2
1 2

 #include<iostream>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<set>

 #define maxn 100005

 #define MAXN 10005

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

 const int N=;

 const int M=;

 const int INF=0x3f3f3f3f;

 using namespace std;

 inline int read()

 {

     char ch=' ';

     int ans=;

     while(ch<'' || ch>'')

         ch=getchar();

     while(ch<='' && ch>='')

     {

         ans=ans*+ch-'';

         ch=getchar();

     }

     return ans;

 }

 int n;

 vector<pair<int,int> >ve[maxn];

 int dis[maxn],dis1[maxn],dis2[maxn],vis[maxn];

 int a[maxn],b[maxn],c[maxn];

 struct sair{

     int pos,len;

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

         return a.len>b.len;

     }

 };

 void Dijstra(int s){

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

         dis[i]=INF;

         vis[i]=;

     }

     priority_queue<sair>Q;

     sair tmp;

     tmp.pos=s,tmp.len=;

     Q.push(tmp);

     dis[s]=;

     int now,Ne,len;

     while(!Q.empty()){

         tmp=Q.top();

         Q.pop();

         now=tmp.pos;

         if(!vis[now]){

             vis[now]=;

             for(int i=;i<ve[now].size();i++){

                 Ne=ve[now][i].first;

                 len=ve[now][i].second;

                 if(dis[Ne]>dis[now]+len){

                     dis[Ne]=dis[now]+len;

                     tmp.pos=Ne;

                     tmp.len=dis[Ne];

                     Q.push(tmp);

                 }

             }

         }

     }

 }

 struct Edge{

     int v,next;

     int cap,flow;

 }edge[MAXN*];//注意这里要开的够大。。不然WA在这里真的想骂人。。问题是还不报RE。。

 int cur[MAXN],pre[MAXN],gap[MAXN],path[MAXN],dep[MAXN];

 int cnt=;//实际存储总边数

 void isap_init()

 {

     cnt=;

     memset(pre,-,sizeof(pre));

 }

 void isap_add(int u,int v,int w)//加边

 {

     edge[cnt].v=v;

     edge[cnt].cap=w;

     edge[cnt].flow=;

     edge[cnt].next=pre[u];

     pre[u]=cnt++;

 }

 void add(int u,int v,int w){

     isap_add(u,v,);

     isap_add(v,u,);

 }

 bool bfs(int s,int t)//其实这个bfs可以融合到下面的迭代里，但是好像是时间要长

 {

     memset(dep,-,sizeof(dep));

     memset(gap,,sizeof(gap));

     gap[]=;

     dep[t]=;

     queue<int>q;

     while(!q.empty())

     q.pop();

     q.push(t);//从汇点开始反向建层次图

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         for(int i=pre[u];i!=-;i=edge[i].next)

         {

             int v=edge[i].v;

             if(dep[v]==-&&edge[i^].cap>edge[i^].flow)//注意是从汇点反向bfs，但应该判断正向弧的余量

             {

                 dep[v]=dep[u]+;

                 gap[dep[v]]++;

                 q.push(v);

                 //if(v==sp)//感觉这两句优化加了一般没错，但是有的题可能会错，所以还是注释出来，到时候视情况而定

                 //break;

             }

         }

     }

     return dep[s]!=-;

 }

 int isap(int s,int t)

 {

     if(!bfs(s,t))

     return ;

     memcpy(cur,pre,sizeof(pre));

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

     //cout<<"cur "<<cur[i]<<endl;

     int u=s;

     path[u]=-;

     int ans=;

     while(dep[s]<n)//迭代寻找增广路

     {

         if(u==t)

         {

             int f=INF;

             for(int i=path[u];i!=-;i=path[edge[i^].v])//修改找到的增广路

                 f=min(f,edge[i].cap-edge[i].flow);

             for(int i=path[u];i!=-;i=path[edge[i^].v])

             {

                 edge[i].flow+=f;

                 edge[i^].flow-=f;

             }

             ans+=f;

             u=s;

             continue;

         }

         bool flag=false;

         int v;

         for(int i=cur[u];i!=-;i=edge[i].next)

         {

             v=edge[i].v;

             if(dep[v]+==dep[u]&&edge[i].cap-edge[i].flow)

             {

                 cur[u]=path[v]=i;//当前弧优化

                 flag=true;

                 break;

             }

         }

         if(flag)

         {

             u=v;

             continue;

         }

         int x=n;

         if(!(--gap[dep[u]]))return ans;//gap优化

         for(int i=pre[u];i!=-;i=edge[i].next)

         {

             if(edge[i].cap-edge[i].flow&&dep[edge[i].v]<x)

             {

                 x=dep[edge[i].v];

                 cur[u]=i;//常数优化

             }

         }

         dep[u]=x+;

         gap[dep[u]]++;

         if(u!=s)//当前点没有增广路则后退一个点

         u=edge[path[u]^].v;

      }

      return ans;

 }

 int main(){

     int T;

     T=read();

     while(T--){

         int m;

         n=read();

         m=read();

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

             ve[i].clear();

         }

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

             a[i]=read();

             b[i]=read();

             c[i]=read();

         }

         int s,t;

         s=read();

         t=read();

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

              if(a[i]!=b[i])

             ve[a[i]].push_back(make_pair(b[i],c[i]));

         }

         Dijstra(s);

         memcpy(dis1,dis,sizeof(dis));

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

             ve[i].clear();

         }

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

             if(a[i]!=b[i])

             ve[b[i]].push_back(make_pair(a[i],c[i]));

         }

         Dijstra(t);

         memcpy(dis2,dis,sizeof(dis));

         isap_init();

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

             if(a[i]!=b[i]&&dis1[a[i]]+dis2[b[i]]+c[i]==dis1[t]){

                 add(a[i],b[i],);

             }

         }

         int ans=;

         ans=isap(s,t);

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

     }

 }