#include <iostream>
#include <stdio.h>
#include <string.h>
#include <fstream>
#include <queue>
#define maxn 5000
#define maxe 200000
#define inf 0x7fffffff
using namespace std;
int n,m,ecnt,box[maxn+10];
struct node
{
    int to,next,w,cap;
}edge[maxe+10];
void make(int a,int b,int w,int cap)
{
    edge[ecnt].to=b;
    edge[ecnt].w=w;
    edge[ecnt].cap=cap;
    edge[ecnt].next=box[a];
    box[a]=ecnt++;
}
void make_map(int a,int b,int w)
{
    make(a,b,w,w);
    make(b,a,0,w);
}
int level[maxn+10],p[maxn+10];
bool makelevel(int s,int t)
{
    queue<int> q;
    int i;
    memset(level,-1,sizeof(level));
    level[s]=0;
    q.push(s);
    bool flag=false;
    while(!q.empty())
    {
        int tmp=q.front();q.pop();
        for(i=box[tmp];i+1;i=edge[i].next)
        {
            if(edge[i].w&&level[edge[i].to]==-1)
            {
                level[edge[i].to]=level[tmp]+1;
                q.push(edge[i].to);
                if(edge[i].to==t)
                {
                    flag=true;
                    break;
                }
            }
        }
        if(flag)break;
    }
    for(i=s;i<=t;i++)p[i]=box[i];
    return flag;
}
int dinic(int s,int t,int maxc)
{
    if(s==t)return maxc;
    int ret=0,flow;
    for(int i=p[s];i+1;i=edge[i].next)
    {
        p[s]=i;
        if(edge[i].w&&level[edge[i].to]>=level[s]+1)
        {
            flow=dinic(edge[i].to,t,min(maxc-ret,edge[i].w));
            edge[i].w-=flow;
            edge[i^1].w=flow;
            if((ret+=flow)==maxc)return ret;
        }
    }
    return ret;
}
int color[maxn+10];
void dfs1(int x)
{
    int i;
    color[x]=1;
    for(i=box[x];i+1;i=edge[i].next)
    {
        if(i%2==0&&edge[i].w&&!color[edge[i].to])
        {
            dfs1(edge[i].to);
        }
    }
    return;
}
void dfs2(int x)
{
    int i;
    color[x]=2;
    for(i=box[x];i+1;i=edge[i].next)
    {
        if(i%2&&edge[i].w!=edge[i].cap&&!color[edge[i].to])
        {
            dfs2(edge[i].to);
        }
    }
    return;
}
int min_flow(int s,int t)
{
    int ans=0,cnt=0;
    while(makelevel(s,t))
    {
        ans+=dinic(s,t,inf);
    }
    memset(color,0,sizeof(color));
    dfs1(s);
    dfs2(t);
    int i,j;
    for(i=s;i<=t;i++)
    {
        for(j=box[i];j+1;j=edge[j].next)
        {
            if(j%2==0&&color[i]==1&&color[edge[j].to]==2)//因为少了j%2==0这句话 我wa了20次
            {
                cnt++;
            }
        }
    }
    return cnt;
}
int main()
{
   // freopen("in.txt","r",stdin);
    int i,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ecnt=0;
        memset(box,-1,sizeof(box));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            make_map(a,b,c);
        }
       printf("%d\n",min_flow(0,n-1));
    }
    return 0;
}