nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow)
break;
}
if(!nowflow)
deep[s] = 0;
return nowflow;
}
int DINIC(int s ,int t ,int n)
{
int ans = 0;
while(BFS_DEEP(s ,t ,n))
{
ans += DFS_MAX_FLOW(s ,t ,inf);
}
return ans;
}
void DFS(int s)
{
for(int k = list[s] ;k ;k = E[k].next)
{
int to = E[k].to;
if(mark[to] || !E[k].cost)
continue;
mark[to] = 1;
DFS(to);
}
return ;
}
int main ()
int n ,m ,i ,j ,t;
int a ,b ,c;
scanf("%d" ,&t);
while(t--)
{
memset(list ,0 ,sizeof(list));
tot = 1;
scanf("%d %d" ,&n ,&m);
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d" ,&a ,&b ,&c);
add(a ,b ,c);
edge[i].a = a ,edge[i].b = b ,edge[i].c = c;
}
int ans = DINIC(1 ,n ,n);
mks_ = mkh_ = 0;
memset(mark ,0 ,sizeof(mark));
mark[1] = 1;
DFS(1);
for(i = 2 ;i < n ;i ++)
if(mark[i]) mks[++mks_] = i;
else mkh[++mkh_] = i;
for(i = 1 ;i <= mks_ ;i ++)
for(j = 1 ;j <= mkh_ ;j ++)
{
a = mks[i] ,b = mkh[j];
memset(list ,0 ,sizeof(list));
tot = 1;
for(int k = 1 ;k <= m ;k ++)
add(edge[k].a ,edge[k].b ,edge[k].c);
add(a ,b ,inf);
int tmp = DINIC(1 ,n ,n);
if(ans < tmp) ans = tmp;
}
printf("%d\n" ,ans);
}
return 0;
}