#include <iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define N 1001
#define inf 100000000
int c[N][N],F[N][N],flow,b[N],q[N],n,m,i,j,k,d[N],t[N],x,y,z,fm;
///c[i][j]=capacitatea muchiei (i,j);
///F[i][j]=fluxul de pe muchia (i,j);
///d[i]=gradul nodului i;
///t[i]=tatal lui i in arborele BF
vector<int>a[N];
int BF()
{
    int x,y;
    memset(b,0,(n+1)*sizeof(int));
    q[0]=2;
    q[1]=1;
    b[1]=1;
    for(i=1;i<q[0];++i)
    {
        x=q[i];
        if(x==n)continue;///daca am ajuns in n nu mai am unde sa ma duc;
        for(j=0;j<d[x];++j)
        {
            y=a[x][j];
            if(c[x][y]==F[x][y]||b[y])continue; ///y e deja selectat sau muchia (x,y) e saturata si nu mai pot sa adaug
            b[y]=1;
            t[y]=x;
            q[q[0]++]=y;
        }
    }
    return b[n];///functia returneaza 1 daca exista drum intre start si finish cu toate muchiile nesaturate
    ///0 daca nu exista drum
}
int main()
{
    ifstream f("maxflow.in");
    f>>n>>m;
    while(m--)
    {
        f>>i>>j>>z;
        c[i][j]=z;
        a[i].push_back(j);
        a[j].push_back(i);
        ++d[i];++d[j];
    }
    for(flow=0;BF();)
    {
        for(i=0;i<d[n];++i)///verific toate nodurile din care pot ajunge in n,pentru optimizarea timpului
        {
            x=a[n][i];
            if(!b[x]||F[x][n]==c[x][n])continue;///daca muchia (x,n) e saturata sau daca, facand BF,
            ///nu am ajuns in x trec mai departe pentru ca nu pot utiliza muchia
            fm=inf;///in fm retin diferenta minima dintre capacitatea muchiei si fluxul actual pentru a
            ///o putea adauga ulterior la fluxul fiecarei muchii de pe drum astfel incat la nicio muchie fluxul sa
            ///nu treaca peste capacitatea acesteia
            t[n]=x;///marchez provizoriu tatal lui n ca fiind x pentru a reconstrui drumul
            for(j=n;j!=1;j=t[j])
            fm=min(fm,c[ t[j] ][ j ] - F[ t[j] ][ j ]);
            if(!fm)continue;///daca am o muchie deja saturata in drum inseamna ca nu mai pot sa adaug flux
            for(j=n;j!=1;j=t[j])
            {
                F[ t[j] ][ j ]+=fm;
                F[ j ][ t[j] ]-=fm;///scad fluxul din muchiile de intoarcere(in cazul in care in retea sunt muchii cu
                ///sens opus fata de restul drumului;
            }
            flow+=fm;///contorizez fluxul adaugat;
        }
    }
    ofstream g("maxflow.out");
    g<<flow;
    return 0;
}