#include <fstream>
#include <cmath>
int n,m,s,d,viz[50],Q[50];
int C[50][50];///capacitatea fiecarui arc
int F[50][50];///fluxul fiecarui arc
using namespace std;
void citire()
{
    ifstream f("maxflow.in");
    int i,x,y,c;
    f>>n>>m;
    s=1;
    d=n;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        C[x][y]=c;

    }
}
void afisare()
{
    ofstream g("maxflow.out");
    int i,j,vf=0;
    for(i=1; i<=n;i++)
        vf+=F[i][d];
    g<<vf;

}
int bfs()
{   ///returneaza 1 daca iesirea retelei nu a fost marcata
    int p,u,i,x;
    Q[0]=s;p=u=0;viz[s]=1;
    while (p<=u && !viz[d])
    {
        x=Q[p++];
        for(i=1; i<=n;i++)
            if(!viz[i])
            if (F[x][i]<C[x][i])
        {
            viz[i]=x; Q[++u]=i;
        }
        else if(F[i][x>0])
            {
            viz[i]=-x; Q[++u]=i;
        }
    }
    return !viz[d];
}
void Edmonds_Karp()
{
    int a,b,i,lg,v;
    int L[50];
    do
    {
     ///marcam varfurile intr-o parcurgere in latime
     for(i=1; i<=n;i++) viz[i]=0;
     if (bfs()) return;
     ///determinam lantul de ameliorare in vectorul L
     L[0]=d; lg=0;
     a=b=10000;
     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(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 main()
{
    citire();
    Edmonds_Karp();
    afisare();
    return 0;
}