#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+7;
struct node{
    int from,v,len;
    node(int f=0,int v=0,int len=0):from(f),v(v),len(len){}
    bool operator <(const node &a)const{
        return len>a.len;
    }
};
const int maxn=1e4+5;
vector<int>G[maxn];
vector<int>fa[maxn];
node edges[maxn*2];
int indxe;
int dis[maxn];
bool vis[maxn];
void init(){
    for(int i=0;i<maxn;i++){
        G[i].resize(0);
        vis[i]=false;
        dis[i]=INF;
    }
}
#define ll long long
ll dij(int s,int e){
    priority_queue<node>pq;
    pq.push(node(s,0));
    dis[s]=0;
    int v,v2,len;
    while(!pq.empty()){
        node now=pq.top();
        pq.pop();
        v=now.v;
        if(vis[v])continue;
        vis[v]=1;
        for(int i=0;i<G[v].size();i++){
            v2=edges[G[v][i]].v;
            len=edges[G[v][i]].len;
            if(!vis[v2]&&dis[v2]>dis[v]+len){
                fa[v2].resize(0);
                fa[v2].push_back(G[v][i]);
                dis[v2]=dis[v]+len;
                pq.push(node(v2,dis[v2]));
            }
            else if(!vis[v2]&&dis[v2]==dis[v]+len){
                fa[v2].push_back(G[v][i]);
            }
        }
    }
    return dis[e];
}
int N,M,S,T,x,y,c,ans;
int W[maxn*2],To[maxn*2],cnt;
int l[maxn*5],h,t,dist[maxn];
vector <int> a[maxn];
bool BFS(){
    h=t=0;
    l[++t]=S;
    memset(dist,0,sizeof(dist));
    dist[S]=1;
    while(h<t){
        int frot=l[++h];
        for(int i=0;i<a[frot].size();i++){
            int to=a[frot][i];
            if(!dist[To[to]] && W[to]){
                dist[To[to]]=dist[frot]+1;
                l[++t]=To[to];
            }
        }
        //cout<<h<<' '<<t<<endl;
    }
    return dist[T];
}
int find(int now,int x){
    if(now==T)
        return x;
    for(int i=0;i<a[now].size();i++){
        int to=a[now][i];
        if(dist[To[to]]==dist[now]+1 && W[to]){
            int fd=find(To[to],min(x,W[to]));
            if(fd){
                W[to]-=fd;
                W[to^1]+=fd;
                return fd;
            }
        }
    }
    return 0;
}
set<int>st;
void add_v(int p){
    if(st.count(p))return;
    if(p==1){
        //st.insert(1);
        return;
    }
    //st.insert(p);
    queue<int>q;
    q.push(p);
    memset(vis,0,sizeof vis);
    while(!q.empty()){
        p=q.front();q.pop();
        if(vis[p])continue;
        vis[p]=1;
        for(int i=0;i<fa[p].size();i++){
            st.insert(fa[p][i]);
            q.push(edges[fa[p][i]].from);
        }
    }
    return;
}
int n,m,indx;
int ys[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        init();
        cin>>n>>m;
        indxe=0;
        for(int i=0;i<m;i++){
            cin>>x>>y>>c;
            //cout<<x<<endl;
            edges[indxe]=node(x,y,c);
            G[x].push_back(indxe++);
            edges[indxe]=node(y,x,c);
            G[y].push_back(indxe++);
            //cout<<x<<' '<<y<<' '<<c<<endl;
        }
        if(dij(1,n)==INF){
            cout<<0<<endl;
            continue;
        }
        //cout<<dij(1,n)<<endl;
        st.clear();
        add_v(n);
        /*
        indx=0;
        for(auto x:st){
            indx++;
            ys[x]=indx;
        }*/
        cnt=0;
        S=1,T=n;
        for(int i=1;i<=n;i++){
            a[i].resize(0);
        }
        //for(int i=1;i<=n;i++){
            //a[i].resize(0);
            //if(!st.count(i))continue;
        for(auto p:st){
            x=edges[p].from;
            y=edges[p].v;
            c=edges[p].len;
            cout<<"dd"<<x<<' '<<y<<' '<<c<<endl;
            W[cnt]=c,To[cnt]=y;a[x].push_back(cnt);cnt++;
            W[cnt]=0,To[cnt]=x;a[y].push_back(cnt);cnt++;
        }

        while(BFS())
        {
            ans+=find(S,2e9);
            //cout<<ans<<endl;
        }
        printf("%d\n",ans);
    }
    return 0;
}
