#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, delta;

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){
    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, hmin;
    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();
    bool flag;
    bool is_change = false;
    while(true){
        is_change = false;
        for(node = 2 ; node < n ; node++){
            while(true){
                if(e[node] <= 0) break;
                flag = false;
                for(auto &it : v[node])
                    if(e[node] > 0 && cf[node][it] > 0 && h[node] == h[it] + 1){
                        pompare(node, it);
                        is_change = true;
                        flag = true;
                    }

                if(flag) continue;
                hmin = inf;
                for(auto &it : v[node])
                    if(cf[node][it] > 0)
                        hmin = min(hmin, h[it]);

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

                if(flag) continue;

                break;
            }

        }

        if(!is_change)
            break;


    }


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