#include <fstream>
#define NMAX 1010
#include <queue>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

struct elem{int vecin;int c;int f;} M[NMAX][NMAX],MT[NMAX][NMAX];
int grad_plecare[NMAX],grad_intrare[NMAX],use[NMAX],v[NMAX];
int n,m,indice;
int v1,v2,v_final;
queue <int> C;

void ameliorare_lant();
int BFS();
void curata();
int minim(int a,int b)
{
    if(a<b) return a;
    return b;
}
int vecini(int a,int b,int c);

int main()
{
    int i,x,y,c,s=0;
    fin >> n >> m;
    for(i=1;i<=m;i++)
    {
        fin >> x >> y >> c;
        grad_plecare[x]++;
        M[x][grad_plecare[x]].vecin=y;
        M[x][grad_plecare[x]].c=c;

        grad_intrare[y]++;
        MT[y][grad_intrare[y]].vecin=x;
        MT[y][grad_intrare[y]].c=c;

    }
    while(BFS())//1 daca am atins si 0 daca nu nodul de final
    {
        //in v determin vectorul de marcaje in BFS
        ameliorare_lant();
        //ameliorare lant si sterg marcaje pt tura viitoare

    }
    for(i=1;i<=grad_intrare[n];i++)
        s+=MT[n][i].f;
    fout << s <<'\n';
    return 0;
}

void ameliorare_lant()
{
    int i,curent=n,unde,poz,cat;
    v1=99999999;
    v2=99999999;
    for(i=1;i<=indice;i++)//3 6 1 exemplu
    {
        if(v[i]>0)
        {
            unde=v[i];//daca e pozitiv
            //arc 3->4
            poz=vecini(unde,curent,1);
            cat=M[unde][poz].c-M[unde][poz].f;
            if(cat<v1)
                v1=cat;
        }
        else
        {
            unde=-v[i];
            poz=vecini(unde,curent,2);
            //arc 3<-4
            cat=MT[unde][poz].f;
            if(cat<v2)
                v2=cat;
        }
        curent=unde;
    }
    v_final=minim(v1,v2);
    //acum actualizez
    curent=n;
    for(i=1;i<=indice;i++)
    {
        if(v[i]>0)
        {
            unde=v[i];//daca e pozitiv
            //arc 3->4
            poz=vecini(unde,curent,1);
            M[unde][poz].f+=v_final;
            poz=vecini(curent,unde,2);
            MT[curent][poz].f+=v_final;
        }
        else
        {
            unde=-v[i];
            poz=vecini(unde,curent,2);
            //arc 3<-4
            MT[unde][poz].f-=v_final;
             poz=vecini(curent,unde,1);
            M[curent][poz].f-=v_final;
        }
        curent=unde;
    }
}

int vecini(int a,int b,int tip)
{//plec de la a la b de tip 1(adica umblu in M cu grad_plecare) si de tip 2(umblu in MT cu grad_intoarcere)
    int i;
    if(tip==1)
    {
        for(i=1;i<=grad_plecare[a];i++)
            if(M[a][i].vecin==b)
                return i;
    }
    else
    {
        for(i=1;i<=grad_intrare[a];i++)
            if(MT[a][i].vecin==b)
             return i;
    }
    return 0;
}

int BFS()
{
    int i,val,ok;
    //intotdeauna plec din 1
    curata();//coada si use
    C.push(1);
    use[1]=1;
    ok=1;
    while(C.size()!=0 && ok==1)
    {
        val=C.front();
        C.pop();
        for(i=1;i<=grad_plecare[val];i++)
            if(use[M[val][i].vecin]==0 && M[val][i].f!=M[val][i].c)
            {
                use[M[val][i].vecin]=val;
                C.push(M[val][i].vecin);
                if(i==n)
                {
                    ok=0;
                    break;
                }
            }
        for(i=1;i<=grad_intrare[val];i++)
            if(use[MT[val][i].vecin]==0 && MT[val][i].f!=MT[val][i].c)
            {
                use[MT[val][i].vecin]=-val;
                C.push(MT[val][i].vecin);
                if(i==n)
                {
                    ok=0;
                    break;
                }

            }
    }
    if(use[n]!=0)
    {
        //reconstruiesc drumul si ies
        val=use[n];
        indice=1;
        while(val!=1)
        {
            v[indice]=val;
            indice++;
            if(val<0) val=-val;//nu is sigur aici
            val=use[val];
        }
        v[indice]=val;
        return 1;
    }
    return 0;
}

void curata()
{
    int i;
    while(C.size())
        C.pop();
    for(i=1;i<=n;i++)
        use[i]=0;
}