#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<memory>
#include<cstring>
using namespace std;
const int inf = 2000000000;
const int maxn = 505;
const int maxm = 5005;

struct Edge{
    int u,v,val;
    int next;
    Edge(){}
    Edge(int u,int v,int next,int val=0):u(u),v(v),next(next),val(val){}
}edg[maxm<<1];
int tot,head[maxn];
void add(int u,int v,int flow = 0){
    edg[tot] = Edge(u,v,head[u],flow);
    head[u] = tot++;
    edg[tot] = Edge(v,u,head[v]);
    head[v] = tot++;
}

int st,en,nv;//注意：如果遇到边那些都对，但是最大流是0，一般是这里忘记了 
int cur[maxn],pre[maxn],dis[maxn],gap[maxn],q[maxn];
void predis()
{
    int i,u,v,l,r=0;
    for(i=0; i<=nv; ++i)dis[i]=-1,gap[i]=0;
    gap[dis[q[r++]=en]=0]=1;
    for(l=0; l<r; ++l)
        for(i=head[u=q[l]]; i!=-1; i=edg[i].next)
            if(edg[i^1].val && dis[v=edg[i].v]<0)
                ++gap[dis[q[r++]=v]=dis[u]+1];
}
int Sap( int st, int en ){
    predis();//预处理分层，dis[] gap[]删了；其余不变 
    int u = pre[st] = st,maxflow = 0,aug = inf;
    for(int i=0;i<=nv;++i)cur[i]=head[i];
    while( dis[st] < nv )
    {
loop:    for( int &i = cur[u]; i != -1 ; i = edg[i].next ) {//无敌取地址符&，节约一行代码cur[u]=i;
            int v =edg[i].v;
            if( edg[i].val && dis[u] == dis[v]+1) {
                aug = aug <  edg[i].val? aug: edg[i].val;
                pre[v] = u;
                u = v;
                if( v == en ) {
                    maxflow += aug;
                    for( u = pre[u]; v != st ; v = u,u = pre[u] ) {
                         edg[cur[u]].val -= aug;
                         edg[cur[u]^1].val += aug;
                    }
                    aug = inf;
                }
                goto loop;
            }
        }
        int mindis =  nv;
        for( int i =  head[u]; i != -1 ; i =  edg[i].next ){//变量是i了，wa过一次
            int v = edg[i].v;
            if(  edg[i].val && dis[v] < mindis) {
                cur[u] = i;                 //注意这
                mindis = dis[v];
            }
        }
        if( --gap[dis[u]] == 0 ) break;
        gap[ dis[u] = mindis+1 ]++;    //写成==会死循环
        u = pre[u];
    }
    return maxflow;
}

int col[maxn];
void dfs1(int u){
    col[u] = 1;
    for(int i=head[u];i!=-1;i=edg[i].next){
        int v = edg[i].v;
        if(edg[i].val && !col[v]) dfs1(v);
    }
}
void dfs2(int u){
    col[u] = -1;
    for(int i=head[u];i!=-1;i=edg[i].next){
        int v = edg[i].v;
        if(edg[i^1].val && !col[v]) dfs2(v);
    }
}

int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        memset(head,-1,sizeof(head));
        tot = 0;
        st = 0; en = n -1; nv = n;
        int a,b,c;
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        Sap(st,en);
        
        memset(col,0,sizeof(col));
        dfs1(st); dfs2(en);
        
        int ans = 0;
        for(int i=0;i<tot;i+=2)
            if(!edg[i].val && col[edg[i].u]==1 && col[edg[i].v]==-1) ++ans;
        printf("%d\n",ans);
    }
    return 0;
}