思路：

首先 先Dijkstra一遍 找出来最短路

不是最短路上的边都不要

然后呢 套个Dinic模板就好了……

求个最小割

输出

大功告成~~

//By SiriusRen

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 22222

int n,m,xx,yy,zz,first[N],tot,dis[N],vis[N],ans,cases;

struct Edge{int v,w,next;}edge[N];

struct Node{int now,weight;}jy;

void add(int xx,int yy,int zz){

    edge[tot].v=yy,edge[tot].w=zz;

    edge[tot].next=first[xx],first[xx]=tot++;

}

bool operator < (Node a,Node b){return a.weight>b.weight;}

void Dijkstra(int from){

    memset(vis,0,sizeof(vis));

    memset(dis,0x3f,sizeof(dis));

    dis[from]=0;

    priority_queue<Node>pq;

    jy.now=from,jy.weight=0;

    pq.push(jy);

    while(!pq.empty()){

        Node t=pq.top();pq.pop();

        if(vis[t.now])continue;

        vis[t.now]=1;

        for(int i=first[t.now];~i;i=edge[i].next)

            if(!vis[edge[i].v]&&dis[edge[i].v]>dis[t.now]+1){

                dis[edge[i].v]=dis[t.now]+1;

                jy.now=edge[i].v;jy.weight=t.weight+1;

                pq.push(jy);

            }

    }

}

struct Dinic{

    int v[N],next[N],w[N],fst[N],cnt;

    void init(){memset(fst,-1,sizeof(fst)),cnt=0;}

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

        w[cnt]=z,v[cnt]=y;

        next[cnt]=fst[x],fst[x]=cnt++;

    }

    bool tell(){

        memset(vis,-1,sizeof(vis));

        queue<int>q;

        q.push(1),vis[1]=0;

        while(!q.empty()){

            int t=q.front();q.pop();

            for(int i=fst[t];~i;i=next[i]){

                if(w[i]&&vis[v[i]]==-1)

                    q.push(v[i]),vis[v[i]]=vis[t]+1;

            }

        }

        return vis[n]!=-1;

    }

    int zeng(int x,int y){

        if(x==n||!y)return y;

        int r=0;

        for(int i=fst[x];~i&&y>r;i=next[i])

            if(w[i]&&vis[v[i]]==vis[x]+1){

                int t=zeng(v[i],min(y-r,w[i]));

                w[i]-=t,w[i^1]+=t,r+=t;

            }

        if(!r)vis[x]=-1;

        return r;

    }

    void flow(){

        while(tell())while(xx=zeng(1,0x3fffffff))ans+=xx;

        printf("%d\n",ans);

    }

}dinic;

int main(){

    scanf("%d",&cases);

    while(cases--){

        memset(first,-1,sizeof(first)),tot=ans=0;

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

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

            scanf("%d%d%d",&xx,&yy,&zz);

            add(xx,yy,zz),add(yy,xx,zz);

        }

        Dijkstra(1),dinic.init();

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

            for(int j=first[i];~j;j=edge[j].next)

                if(dis[edge[j].v]==dis[i]+1){

                    dinic.add(i,edge[j].v,edge[j].w);

                    dinic.add(edge[j].v,i,0);

                }

        dinic.flow();

    }

}