#include <fstream>
#include <climits>
#include <vector>
#include <deque>
#include <cstring>
#define dim 1010
using namespace std;
vector <int> a[dim];
deque <int> c;
int cost[dim][dim];
int flux[dim][dim];
int f[dim];
int t[dim];
int i,n,m,Min,sol,x,y,z;

int bfs() {
    memset(f,0,sizeof(f));
    c.clear();
    c.push_back(1);
    f[1]=1;
    int ok=0;
    while (!c.empty()) {
        int nod=c.front();
        for (int i=0;i<a[nod].size();i++) {
            int vecin=a[nod][i];
            if (f[vecin]==0&&cost[nod][vecin]>flux[nod][vecin]) {
                c.push_back(vecin);
                f[vecin]=1;
                t[vecin]=nod;
                if (vecin==n) {
                    ok=1;
                }
            }
        }
        c.pop_front();
    }
    return ok;
}

int main() {
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>z;
        a[x].push_back(y);
        a[y].push_back(x);
        cost[x][y]=z;
        ///c[x][y]=capacitatea drumului de la x la y
        ///c[y][x]=0
    }
    while (bfs()) {
        for (int i=0;i<a[n].size();i++) {
            int vecin=a[n][i];
            if (cost[vecin][n]>flux[vecin][n]&&f[vecin]==1) {
                Min=cost[vecin][n]-flux[vecin][n];
                for (x=n;t[x]!=0;x=t[x]) {
                    Min=min(Min,cost[t[x]][x]-flux[t[x]][x]);
                }
                sol+=Min;
                for (x=n;t[x]!=0;x=t[x]) {
                    flux[t[x]][x]+=Min;
                    flux[x][t[x]]-=Min;
                }
            }
        }
    }
    fout<<sol;
    return 0;
}