#include <bits/stdc++.h>
using namespace std;

#define N 1010
int n, c[N][N], f[N][N], m, fv[2*N], p[N];
bool inq[N];
struct node{
    int h, eflow;
} ver[N];
queue <int> Q;

void preFlow(int s){
    for (int i=1; i<=n; i++) ver[i] = {0, 0};
    ver[s].h = n; fv[n]++;
    for (int i=1; i<=n; i++)
        if (s != i && c[s][i]) ver[i].eflow = c[s][i], c[i][s] = c[s][i], c[s][i] = 0, Q.push(i), inq[i] = 1;
}

void push(int q){
    for (int i=1; i<=n && ver[q].eflow; i++){
        if (q == i || !c[q][i]) continue;
        if (ver[q].h > ver[i].h){
            int flow = min(c[q][i], ver[q].eflow);
            ver[q].eflow -= flow;
            ver[i].eflow += flow;
            if (!inq[i]) Q.push(i), inq[i] = 1;
            c[q][i] -= flow;
            c[i][q] += flow;
        }
    }
    return;
}

void normalize_h(int qh){
    if (!fv[qh]){
        for (int i=1; i<=n; i++)
            if (ver[i].h > qh) fv[ver[i].h]--, ver[i].h = qh, fv[qh]++;
    }
}

//this shit is fucking magic
void relabel(int q){
    int mx = 1e9;
    for (int i=1; i<=n; i++)
        if (i != q && c[q][i]) mx = min(mx, ver[i].h);
    ver[q].h = mx + 1;
    /*
    ++ver[q].h;
    fv[ver[q].h - 1]--;
    fv[ver[q].h]++;
    normalize_h(ver[q].h - 1);
    */
}

int maxFlow(int s, int t){
    preFlow(s);
    while (!Q.empty()){
        int u = Q.front();
        Q.pop(); inq[u] = 0;
        if (!ver[u].eflow || u == t || u == s) continue;
        while (ver[u].eflow){
            push(u);
            if (ver[u].eflow) relabel(u); //and this shit
        }
    }
    return ver[t].eflow;
}

bool bfs(){
    for (int i=1; i<=n; i++) inq[i] = 0;
    inq[1] = 1; Q.push(1);
    while (!Q.empty()){
        int nod = Q.front();
        Q.pop();
        if (nod == n) continue;
        for (int i=1; i<=n; i++)
            if (!inq[i] && i != nod && c[nod][i]){
                p[i] = nod; Q.push(i); inq[i] = 1;
            }
    }
    return inq[n];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ifstream cin ("maxflow.in");
    ofstream cout ("maxflow.out");
    cin >> n >> m;
    for (int i=1, x, y, z; i<=m; i++){
        cin >> x >> y >> z;
        c[x][y] += z;
    }
    for (int i=1; i<=n; i++) c[n][i] = c[i][1] = c[i][i] = 0;
    cout << maxFlow(1, n) << '\n';
    /*
    cout << bfs() << '\n';
    ifstream in ("maxflow.out");
    for (int i=1; i<=n; i++)
        for (int j=1, x; j<=n; j++){
            in >> x;
            if (c[i][j] != x) cout << i << ' ' << j << ": " << x << ' ' << c[i][j] << '\n';
        }
    */
    return 0;
}