思路：

求一遍网络流 在残余网络上DFS

从起点DFS 从终点把边反向DFS

一个边跟起点连通 跟终点反向的边连通 ans++

注：此题不能用tarjan 因为有边权为0的边

//By SiriusRen

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 555

#define M 10050

int n,m,xx[M],yy[M],zz[M],first[N],vis[N],next[M],v[M],w[M],tot=2;

int dfn[N],low[N],cnt,stk[N],top,T,jy,p[N],ans;

void Add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}

void add(int x,int y,int z){Add(x,y,z),Add(y,x,0);}

bool tell(){

    memset(vis,-1,sizeof(vis)),vis[0]=0;

    queue<int>q;q.push(0);

    while(!q.empty()){

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

        for(int i=first[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)return y;

    int r=0;

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

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

            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 dfs(int x,bool f,int col){

    vis[x]=col;

    for(int i=first[x];~i;i=next[i])

        if(!vis[v[i]]&&w[i^f])

            dfs(v[i],f,col);

}

int main(){

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

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

    for(int i=1;i<=m;i++)scanf("%d%d%d",&xx[i],&yy[i],&zz[i]),add(xx[i],yy[i],zz[i]);

    while(tell())while(zeng(0,0x3fffffff));

    memset(vis,0,sizeof(vis)),dfs(0,0,1),dfs(n,1,2);

    for(int i=1;i<=m;i++)if(vis[xx[i]]==1&&vis[yy[i]]==2&&!w[i*2])ans++;

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

}