#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1005;
const int inf = 2e9;
vector < int > v[NMAX];
int c[NMAX][NMAX], cf[NMAX][NMAX], edg[NMAX][NMAX], e[NMAX], h[NMAX], n, m;

void initializare_preflux(){
    int s = 1;
    h[s] = n;
    for(auto it : v[s]){
        e[it] += c[s][it];
        cf[s][it] -= c[s][it];
        cf[it][s] += c[s][it];
    }
}

void pompare(int node, int nxt){
    int delta = min(e[node], cf[node][nxt]);
    e[node] -= delta;
    e[nxt] += delta;
    cf[node][nxt] -= delta;
    cf[nxt][node] += delta;
}

int main(){
    int node, i, x, y, z;
    f >> n >> m;
    while(m--){
        f >> x >> y >> z;
        v[x].push_back(y);
        v[y].push_back(x);

        edg[x][y] = 1;
        c[x][y] += z;
        cf[x][y] += z;
    }

    initializare_preflux();

    while(true){
        bool flag = false;
        for(node = 2 ; node < n && !flag ; node++){
            if(e[node] <= 0) continue;
            for(auto it : v[node])
                if(cf[node][it] > 0 && h[node] == h[it] + 1){
                    pompare(node, it);
                    flag = true;
                }
        }

        if(flag) continue;

        for(node = 2 ; node < n && !flag ; node++){
            if(e[node] <= 0) continue;

            int hmin = inf;
            for(auto it : v[node])
                if(cf[node][it])
                    hmin = min(hmin, h[it]);

            if(hmin >= h[node]){
                h[node] = hmin + 1;
                flag = true;
            }
        }

        if(flag) continue;

        break;

    }
    g << e[n];
    return 0;
}