1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 10005

  4 #define ll long long

  5 struct ji{

  6     int nex,to,len;

  7 }edge[N<<1];

  8 vector<ji>v;

  9 queue<int>q;

 10 int E,t,n,m,x,y,z,head[N],d[N],work[N];

 11 ll d1[N],d2[N];

 12 struct ji2{

 13     int k;

 14     bool operator < (const ji2 &a)const{

 15         return d1[k]>d1[a.k];

 16     }

 17 };

 18 priority_queue<ji2>qq;

 19 void add(int x,int y,int z){

 20     edge[E].nex=head[x];

 21     edge[E].to=y;

 22     edge[E].len=z;

 23     head[x]=E++;

 24 }

 25 void dij(int k){

 26     memset(d1,0x3f,sizeof(d1));

 27     qq.push(ji2{k});

 28     d1[k]=0;

 29     while (!qq.empty()){

 30         k=qq.top().k;

 31         qq.pop();

 32         for(int i=head[k];i!=-1;i=edge[i].nex){

 33             if (d1[k]+edge[i].len<d1[edge[i].to]){

 34                 d1[edge[i].to]=d1[k]+edge[i].len;

 35                 qq.push(ji2{edge[i].to});

 36             }

 37         }

 38     }

 39 }

 40 bool bfs(){

 41     memset(d,-1,sizeof(d));

 42     q.push(1);

 43     d[1]=0;

 44     while (!q.empty()){

 45         int k=q.front();

 46         q.pop();

 47         for(int i=head[k];i!=-1;i=edge[i].nex){

 48             int v=edge[i].to;

 49             if ((edge[i].len)&&(d[v]<0)){

 50                 d[v]=d[k]+1;

 51                 q.push(v);

 52             }

 53         }

 54     }

 55     return d[n]>=0;

 56 }

 57 int dfs(int k,int s){

 58     if (k==n)return s;

 59     int p;

 60     for(int i=work[k];i!=-1;i=edge[i].nex){

 61         int v=edge[i].to;

 62         if ((edge[i].len)&&(d[v]==d[k]+1)&&(p=dfs(v,min(s,edge[i].len)))){

 63             edge[i].len-=p;

 64             edge[i^1].len+=p;

 65             work[k]=i;

 66             return p;

 67         }

 68     }

 69     work[k]=-1;

 70     return 0;

 71 }

 72 ll dinic(){

 73     int k;

 74     ll ans=0;

 75     while (bfs()){

 76         memcpy(work,head,sizeof(head));

 77         while (k=dfs(1,0x3f3f3f3f))ans+=k;

 78     }

 79     return ans;

 80 }

 81 int main(){

 82     scanf("%d",&t);

 83     while (t--){

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

 85         if (n==1){

 86             printf("0\n");

 87             continue;

 88         }

 89         E=0;

 90         memset(head,-1,sizeof(head));

 91         v.clear();

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

 93             scanf("%d%d%d",&x,&y,&z);

 94             add(x,y,z);

 95             v.push_back(ji{x,y,z});

 96         }

 97         dij(1);

 98         memcpy(d2,d1,sizeof(d1));

 99         E=0;

100         memset(head,-1,sizeof(head));

101         for(int i=0;i<v.size();i++)add(v[i].to,v[i].nex,v[i].len);

102         dij(n);

103         v.clear();

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

105             for(int j=head[i];j!=-1;j=edge[j].nex)

106                 if (d1[i]+d2[edge[j].to]+edge[j].len==d1[1])v.push_back(ji{edge[j].to,i,edge[j].len});

107         E=0;

108         memset(head,-1,sizeof(head));

109         for(int i=0;i<v.size();i++){

110             add(v[i].nex,v[i].to,v[i].len);

111             add(v[i].to,v[i].nex,0);

112         }

113         printf("%lld\n",dinic());

114     }

115 }