//#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#define nmax 1001
#define mmax 5001
using namespace std;
FILE *fi=fopen("maxflow.in","r"),*g=fopen("maxflow.out","w");
int c[nmax][nmax],f[nmax][nmax],n,m,len,t[nmax],s,d;
long long flux;
vector <int> l[nmax];
int bfs()
{
    queue <int> q;
    int i,k,ok=0;
    for(i=1;i<=n;i++)
        t[i]=0;
    t[s]=-1;
    q.push(s);
    for(;!q.empty();q.pop())
    {
        k=q.front();
        for(i=0;i<l[k].size();i++)
            if(t[ l[k][i] ]==0 && c[k][ l[k][i] ]>f[k][ l[k][i] ])
            {
                if(l[k][i]!=d)
                    {t[ l[k][i] ]=k;
                    q.push(l[k][i]);}
                else ok=1;
            }
    }
    return ok;
}
void dinic()
{
    int i,j,mini,pas;
    for(pas=bfs();pas>0;pas=bfs())
    {
        for(i=0;i<l[d].size();i++)
            if(t[l[d][i]]>0&&c[ l[d][i] ][d]>f[ l[d][i] ][d])
        {
            mini=110001;
            t[d]=l[d][i];
            for(j=d;j!=s;j=t[j])
                if(mini>c[ t[j] ][j]-f[ t[j] ][j])
                mini=c[ t[j] ][j]-f[ t[j] ][j];
            if(mini>0)
            {
                flux+=mini;
                for(j=d;j!=s;j=t[j])
                    {f[t[j]][j]+=mini;
                    f[j][t[j]]-=mini;}
            }
        }
    }
}
int main()
{
    int i,x,y;
    fscanf(fi,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fi,"%d %d",&x,&y);
        l[x].push_back(y);
        l[y].push_back(x);
        fscanf(fi,"%d",&c[x][y]);
    }
    fclose(fi);
    s=1; d=n;
    dinic();
    fprintf(g,"%lld",flux);
    fclose(g);
    return 0;
}