#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define NMax 1005
#define inf 2100000000

ifstream f("maxflow.in");
ofstream g("maxflow.out");

int n,m;
vector<int> v[NMax];
int C[NMax][NMax],F[NMax][NMax];
bool viz[NMax];
int ant[NMax];

int BFS()
{
    queue<int> cd;
    int i,s,semn,nod,nod2;
    int a=inf,b=inf,c;

    for(i=1;i<=n;i++) viz[i]=0;
    viz[1]=1;
    ant[1]=0;
    cd.push(1);
    while(!cd.empty())
    {
        s=cd.front(); cd.pop();

        for(i=0;i<(int)v[s].size();i++) if(!viz[v[s].at(i)] && F[s][v[s].at(i)]<abs(C[s][v[s].at(i)]))
        {
            semn=1;
            if(C[s][v[s].at(i)]<0 && F[s][v[s].at(i)]) semn=-1;

            viz[v[s].at(i)]=1;
            ant[v[s].at(i)]=s*semn;

            if(v[s].at(i)==n)
            {
                nod=n;
                while(ant[nod])
                {
                    nod2=abs(ant[nod]);

                    if(ant[nod]>0) a=min(a,C[nod2][nod]-F[nod2][nod]);
                    else b=min(b,F[nod][nod2]);

                    nod=nod2;
                }

                c=min(a,b);

                nod=n;
                while(ant[nod])
                {
                    nod2=abs(ant[nod]);

                    if(ant[nod]>0) F[nod2][nod]+=c,F[nod][nod2]+=c;
                    else F[nod][nod2]-=c,F[nod2][nod]-=c;

                    nod=nod2;
                }

                return c;
            }

            cd.push(v[s].at(i));
        }
    }

    return 0;
}

int main()
{
    int i;
    int a,b,c;
    int flow,fmin;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        C[a][b]=c;
        C[b][a]=-c;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(flow=0;fmin=BFS();flow+=fmin);

    g<<flow<<"\n";

    f.close();
    g.close();
    return 0;
}