#include<iostream>
#include<fstream>
#define NMAX 1001
#include<vector>
#include<algorithm>
#define inf 1000000
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int tat[NMAX],viz[NMAX],q[NMAX];
int c[NMAX][NMAX],f[NMAX][NMAX];
vector<int>g[NMAX];
int n,m,s,d;
int bfs(void);
void read()
{
    fin>>n>>m;
    s=1;d=n;

    int x,y,ct;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>ct;
        c[x][y]=ct;

    }
    fin.close();
}
void solve()
{
   int L[NMAX],lg,a,b,v;

   do
   {
       for(int i=1;i<=n;i++)viz[i]=0;
       if(bfs())return ;
       L[0]=d;lg=0; a=b=inf;
       while(L[lg]!=s)
       {
           ++lg;
           L[lg]=abs(viz[L[lg-1]]);
           if(viz[L[lg-1]]>0)
           {
               a=min(a,c[L[lg]][L[lg-1]]-f[L[lg]][L[lg-1]]);

           }
           else
            if(viz[L[lg-1]]<0)
           {
               b=min(b,f[L[lg-1]][L[lg]]);
           }
       }
       v=min(a,b);
       for(int i=lg;i>0;i--)
       {
           if(viz[L[i-1]]>0)
           {
               f[L[i]][L[i-1]]+=v;
           }
           else f[L[i-1]][L[i]]-=v;
       }
   }while(1);
}
int bfs()
{
    int st,dr,x;
    q[0]=s;
    st=dr=0;viz[s]=1;
    while(st<=dr&&!viz[d])
    {
        x=q[st++];
        for(int i=1;i<=n;i++)
            if(!viz[i])
        {
            if(c[x][i]>f[x][i])
            {
                viz[i]=x;
                q[++dr]=i;
            }
            else
                if(f[i][x]>0)
            {
                viz[i]=-x;
                q[++dr]=i;
            }
        }
    }
    return !viz[d];
}


int main()
{
    read();
    solve();
    int rez=0;
    for(int i=1;i<=n;i++)
        rez+=f[i][d];
    fout<<rez<<'\n';
fout.close();
return 0;
}