#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define dim 1024
int n, m, coada[dim], t[dim], mat[dim][dim];
int c[dim][dim];//matricea costurilor dintre muchii
vector <int> v[dim];//vectorul cu muchii
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
void read()
{
    int a, b, z, i;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>z;
        c[a][b]=z;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}

int bfs()
{
    memset (t,-1,sizeof (t));
    t[1]=coada[1]=1;
    int inc=1, sf=1;
    while(inc<=sf)
    {
        int x=coada[inc];
        for(int k=0;k<v[x].size();++k)
            if(t[v[x][k]]==-1 && c[x][v[x][k]]!=mat[x][v[x][k]])
            {
                t[v[x][k]]=x;
                coada[++sf]=v[x][k];
            }
        ++inc;
    }
    if(t[n]==-1)
        return 0;
    return 1;
}

void solve()
{
    int flow=0;
    for(;bfs();)
        for(int k=0;k<v[n].size();++k)
            if(c[v[n][k]][n]!=mat[v[n][k]][n])
            {
                int dist=c[v[n][k]][n]-mat[v[n][k]][n];
                for(int i=v[n][k];i!=1;i=t[i])
                    dist=min(dist,c[t[i]][i]-mat[t[i]][i]);
                flow+=dist;
                mat[v[n][k]][n]+=dist;
                mat[n][v[n][k]]-=dist;
                for(int i=v[n][k];i!=1;i=t[i])
                {
                    mat[t[i]][i]+=dist;
                    mat[i][t[i]]-=dist;
                }
            }

            fout<<flow;
}

int main()
{
    read();
    solve();
    return 0;
}