#include <fstream>
#include <deque>
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
ifstream fi("maxflow.in");
ofstream fo("maxflow.out");
 
int n,m,i,j,c[1001][1001],viz[1001],t[1001],f[1001][1001],rs=0;
deque< int > q;
vector< int > g[1001];
 
int BFS(){
     
    for (i=1; i<=n; i++) t[i] = viz[i] = 0;
    q.push_back(1);
    while (!q.empty())
    {
        int nod=q.front(); q.pop_front();
        for (size_t k=0; k<g[nod].size(); k++)
        {
            int v=g[nod][k];
            if (c[nod][v]>f[nod][v] && !viz[v])
            {
                viz[v]=1;
                q.push_back(v);
                t[v]=nod;
            }
        }
    }
     
    return viz[n];
}
 
 
int main(){
     
    fi >> n >> m;
    for (i=1; i<=m; i++)
    {
        int x,y,z;
        fi >> x >> y >> z;
        g[x].push_back(y);
        g[y].push_back(x);
        c[x][y]=z;
    }
     
    while (BFS())
    {
        for (i=1; i<=n; i++)
        {
            if (c[i][n]>f[i][n] && t[i])
            {
                int fmin=c[i][n]-f[i][n];
                for (j=i; j!=1; j=t[j])
                    fmin=min(fmin,(c[t[j]][j]-f[t[j]][j]));
                for (j=i; j!=1; j=t[j])
                {
                    f[t[j]][j]+=fmin;
                    f[j][t[j]]-=fmin;
                }
                f[i][n]+=fmin;
                f[n][i]-=fmin;
                rs+=fmin;
            }
        }
    }
     
    fo << rs;
     
    return 0;
}