#include<fstream>
#include<cstring>
#define nmax 1001
#define inf 1<<30
using namespace std;

struct nod_lista{
    int val;
    nod_lista *link;
};

nod_lista *G[nmax],*Last[nmax];
int T[nmax],Q[nmax],viz[nmax],C[nmax][nmax],F[nmax][nmax];
int N,M,S,D,Flux;

void adauga(int unde,int ce)
{
    nod_lista *q=new nod_lista;
    q->val=ce;
    q->link=NULL;

    if(!G[unde])
    G[unde]=Last[unde]=q;
    else
    {
        Last[unde]->link=q;
        Last[unde]=q;
    }
}

void citeste()
{
    ifstream f("maxflow.in");
    int i,x,y,c;

    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        adauga(x,y);
        adauga(y,x);
        C[x][y]=c;
    }

    S=1,D=N;
    f.close();
}

int BFS(int S,int D)
{
    int p,q,nod;
    nod_lista *it;

    memset(T,0,sizeof(T));
    memset(viz,0,sizeof(viz));

    p=q=0;
    Q[++q]=S;
    viz[S]=1;
    while(p<q)
    {
        nod=Q[++p];
        it=G[nod];
        if(nod!=D)
        while(it)
        {
            if(C[nod][it->val]>F[nod][it->val] && !viz[it->val])
            {
                Q[++q]=it->val;
                viz[it->val]=1;
                T[it->val]=nod;
            }
            it=it->link;
        }
    }

    return viz[D];
}

void satureaza()
{
    int nod,cmin;
    nod_lista *q=G[D];
    while(q)
    {
        nod=q->val;

        if(viz[nod] && C[nod][D]>F[nod][D])
        {
            T[D]=nod;
            cmin=inf;

            nod=D;
            while(nod!=S)
            {
                if(C[T[nod]][nod]-F[T[nod]][nod]<cmin)
                cmin=C[T[nod]][nod]-F[T[nod]][nod];

                nod=T[nod];
            }

            if(cmin>0)
            {

                nod=D;
                while(nod!=S)
                {
                    F[T[nod]][nod]+=cmin;
                    F[nod][T[nod]]-=cmin;
                    nod=T[nod];
                }
                Flux+=cmin;
            }
        }
        q=q->link;
    }
}

void rezolva()
{
    while(BFS(S,D))
    satureaza();
}

void scrie()
{
    ofstream g("maxflow.out");

    g<<Flux<<'\n';
    g.close();
}

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}