#include <iostream>#include <cstring>#include <cstdio>#include <vector>#include <queue>#include <string.h>using namespace std;const int MAXN = 2200;//点数的最大值const int MAXM = 800000;//边数的最大值const int INF2 = 2000000000;struct Edge1{    int to,next,cap,flow;}edge[MAXM];//注意是MAXMint tol;int head[MAXN];int gap[MAXN],dep[MAXN],cur[MAXN];void init(){    tol = 0;    memset(head,-1,sizeof (head));}void add (int u,int v,int w,int rw = 0)//网络流要有反向弧{    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;    edge[tol].next = head[u]; head[u] = tol++;    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;    edge[tol].next = head[v]; head[v] = tol++;}int Q[MAXN];void BFS(int start,int end){    memset(dep,-1,sizeof(dep));    memset(gap,0,sizeof(gap));    gap[0] = 1;    int front = 0, rear = 0;    dep[end] = 0;    Q[rear++] = end;    while(front != rear)    {        int u = Q[front++];        for(int i = head[u]; i !=  -1; i = edge[i].next)        {            int v = edge[i]. to;            if(dep[v] != -1)continue;            Q[rear++] = v;            dep[v] = dep[u] + 1;            gap[dep[v]]++;        }    }}int S[MAXN];int sap(int start,int end, int N)//有几个点{    BFS(start,end);    memcpy(cur,head,sizeof(head));    int top = 0;    int u = start;    int ans = 0;    int i;    while(dep[start] < N)    {        if(u == end)        {            int Min = INF2;            int inser;            for( i = 0;i < top;i++)            {                if(Min > edge[S[i]].cap - edge[S[i]].flow)                {                    Min = edge[S[i]].cap - edge[S[i]].flow;                    inser = i;                }            }            for( i = 0;i < top;i++)            {                edge[S[i]]. flow += Min;                edge[S[i]^1].flow -= Min;            }            ans += Min;            top = inser;            u = edge[S[top]^1].to;            continue;        }        bool flag =  false;        int v;        for( i = cur[u]; i != -1; i = edge[i]. next)        {            v = edge[i]. to;            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])            {                flag =  true;                cur[u] = i;                break;            }        }        if(flag)        {            S[top++] = cur[u];            u = v;            continue;        }        int Min = N;        for( i = head[u]; i !=  -1; i = edge[i].next)        {            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)            {                Min = dep[edge[i].to];                cur[u] = i;            }        }        gap[dep[u]]--;        if(!gap[dep[u]]) return ans;        dep[u] = Min + 1;        gap[dep[u]]++;        if(u != start)u = edge[S[--top]^1].to;    }    return ans;}#define typec inttypec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大bool vis[MAXN];int pre[MAXN];void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg){    for(int i=0;i<n;i++)    {        lowcost[i]=INF;        vis[i]=false;        pre[i]=-1;    }    lowcost[beg]=0;    for(int j=0;j<n;j++)    {        int k=-1;        int Min=INF;        for(int i=0;i<n;i++)            if(!vis[i]&&lowcost[i]<Min)            {                Min=lowcost[i];                k=i;            }        if(k==-1)break;        vis[k]=true;        for(int i=0;i<n;i++)            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])            {                lowcost[i]=lowcost[k]+cost[k][i];                pre[i]=k;            }    }}int cost2[MAXN][MAXN];int dist2[MAXN];int cost[MAXN][MAXN];int num[MAXN][MAXN];int has[MAXN];int dist[MAXN];int main(){    int T;    cin>>T;    while(T--)    {    int n,m;        scanf("%d%d",&n,&m);    {        init();        memset(cost,INF,sizeof cost);        memset(num,0,sizeof num);        for(int i=0;i<n;i++)            cost[i][i]=0;                for(int i=1;i<=m;i++)//双向  有重边        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            u--;            v--;            if(cost[u][v]>w)            {                cost[u][v]=1;                cost[v][u]=1;            }            num[u][v]=w;            num[v][u]=w;                    }        Dijkstra(cost,dist,n,0);// wuxiangda  bulian                                memset(cost2,INF,sizeof cost2);        for(int i=0;i<n;i++)            cost2[i][i]=0;                for(int i=0;i<n;i++)        {            for(int j=0;j<n;j++)            {                if(i!=j)                    if(dist[i]-dist[j]==cost[i][j])                    {                        cost2[j][i]=1;                        add(j,i,num[i][j]);                    }            }        }        Dijkstra(cost2,dist2,n,0);        printf("%d\n",sap(0,n-1,n));    }    }    return 0;}