#include <bits/stdc++.h>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

#define DIM 1000
#define INF (1LL << 30)

int n, m, x, y, cost, flux;
int c[DIM + 1][DIM + 1], f[DIM + 1][DIM + 1], t[DIM + 1];

static inline bool bfs(int s, int d) {
    queue <int> Q;
    for(int i = 1; i <= n; i++)
        t[i] = 0;
    t[s] = -1;
    Q.push(s);
    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        for(int i = 1; i <= n; i++)
            if(!t[i] && c[nod][i] > f[nod][i]) {
                Q.push(i);
                t[i] = nod;
                if(i == d)
                    return 1;
            }
    }
    return 0;
}

///Algoritmul lui Dinic
static inline void Flux_maxim(int s, int d) {
    int r, i;
    for(flux = 0; bfs(s, d);) {
        for(i = 1; i <= n; i++) {
            if(t[i] == -1 || c[i][d] <= f[i][d])
                continue;
            r = c[i][d] - f[i][d];
            for(int j = i; j != s && j; j = t[j])
                r = min(r, c[t[j]][j] - f[t[j]][j]);

            if(r == 0)
                continue;

            f[i][d] += r;
            f[d][i] -= r;
            for(int j = i; j != s; j = t[j]) {
                f[t[j]][j] += r;
                f[j][t[j]] -= r;
            }
            flux += r;
        }
    }
}

int main()
{
    fin.tie(0);
    fout.tie(0);
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        fin >> x >> y >> cost;
        c[x][y] = cost;
    }

    Flux_maxim(1, n);
    fout << flux;

    return 0;
}