//给一个图。给定起点和终点，仅仅能走图上的最短路
//问最多有多少种走的方法。每条路仅仅能走一次
//仅仅要将在最短路上的全部边的权值改为1。求一个最大流即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std ;
const int inf = 0x3f3f3f3f ;
const int maxn = 1010 ;
const int maxm = 1e5+10 ;
int head[maxn] ;
int dis[maxn] ;int n , m ;
int st , en ;int len ;
int nedge ;
int x[maxm] , y[maxm] , z[maxm];
int vis[maxm] ;
struct Edge
{
int v , w ;
int next ;
}edge[maxm<<1] ;
void addedge(int u , int v , int w)
{
edge[nedge].v = v ;
edge[nedge].w = w ;
edge[nedge].next = head[u] ;
head[u] = nedge++ ;
}
void spfa()
{
memset(vis , 0 , sizeof(vis)) ;
queue<int> que ;
for(int i = 1;i <= n;i++)
dis[i] = i == st ?
0 : inf ;
que.push(st) ;vis[st] = 1;
while(que.size())
{
int u = que.front();que.pop() ;
vis[u] = 0 ;
for(int i = head[u];i != -1 ;i = edge[i].next)
{
int v = edge[i].v ;
if(dis[u] + edge[i].w < dis[v])
{
dis[v] = dis[u] + edge[i].w ;
if(!vis[v])
{
que.push(v) ;
vis[v] = 1;
}
}
}
}
}
bool bfs()
{
memset(dis , -1 , sizeof(dis)) ;
dis[st] = 0 ;
queue<int> que ;
que.push(st) ;
while(que.size())
{
int u = que.front();que.pop() ;
for(int i = head[u];i != -1 ;i = edge[i].next)
{
int v = edge[i].v ;
if(dis[v] < 0 && edge[i].w > 0)
{
dis[v] = dis[u] + 1 ;
que.push(v) ;
}
}
}
if(dis[en] > 0)return true ;
return false ;
}
int dfs(int u , int mx)
{
if(u == en)return mx ;
int ans = 0 , a ;
for(int i = head[u];i != -1 ;i = edge[i].next)
{
int v = edge[i].v ;
if(dis[v] == dis[u] + 1 && edge[i].w > 0 && (a = dfs(v , min(mx , edge[i].w))))
{
mx -= a ;
ans += a ;
edge[i].w -= a ;
edge[i^1].w += a ;
if(!mx)break;
}
}
if(!ans)dis[u] = -1 ;
return ans ;
}
int main()
{
//freopen("in.txt" , "r" , stdin) ;
int t ;
scanf("%d" , &t) ;
while(t–)
{
scanf("%d%d" , &n , &m);
memset(head , -1 , sizeof(head)) ;
nedge = 0 ;len = 0 ;
while(m–)
{
int u , v , w ;
scanf("%d%d%d" , &u , &v , &w) ;
if(u != v)
{
addedge(u , v , w) ;
x[len] = u , y[len] = v ,z[len++] = w ;
}
}
scanf("%d%d" , &st , &en) ;
spfa() ;
memset(head , -1 , sizeof(head)) ;
nedge = 0 ;
for(int i = 0;i < len;i++)
if(dis[x[i]] + z[i] == dis[y[i]])
{
addedge(x[i] , y[i] , 1) ;
addedge(y[i] , x[i] , 0) ;
}
int ans = 0 ;
int res ;
while(bfs())
while(res = dfs(st , inf))
ans += res ;
printf("%d\n" , ans) ;
}
return 0 ;
}
