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

/*
int n, m, c[N][N], p[N];
bool viz[N];
queue <int> Q;
vector <int> v[N];

bool bfs(int s, int t){
    for (int i=1; i<=n; i++) viz[i] = 0;
    viz[s] = 1; Q.push(s);
    while (!Q.empty()){
        int nod = Q.front();
        Q.pop();
        if (nod == n) continue;
        for (auto it: v[nod]){
            if (viz[it] || !c[nod][it]) continue;
            viz[it] = 1; Q.push(it); p[it] = nod;
        }
    }
    return viz[t];
}

int EdmondsKarp(int s, int t){
    int maxflow = 0;
    while (bfs(s, t)){
        for (auto it: v[n]){
            if (!viz[it] || !c[it][n]) continue;
            int flow = 1e9;
            p[n] = it;
            for (int nod = t; nod != s; nod = p[nod])
                flow = min(flow, c[p[nod]][nod]);
            for (int nod = t; nod != s; nod = p[nod]){
                c[p[nod]][nod] -= flow;
                c[nod][p[nod]] += flow;
            }
            maxflow += flow;
        }
    }
    return maxflow;
}
*/

#define N 1005
int n, m, c[N][N], fv[2*N];
struct node{
    int eflow, h;
} ver[N];
bool inq[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 (i != s && c[s][i]) Q.push(i), ver[i].eflow += c[s][i], c[i][s] += c[s][i], c[s][i] = 0, inq[i] = 1;
    }
}

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

    }
    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 + 1, fv[qh+1]++;
    }
}

void relabel(int q){
    ver[q].h++;
    fv[ver[q].h - 1]--;
    fv[ver[q].h]++;
    normalize_h(ver[q].h - 1);
}

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

int main(){
    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;
    }
    cout << push_relabel(1, n) << '\n';
    //for (int i=1; i<=n; i++)
    //    if (ver[i].eflow) cout << i << ": " << ver[i].eflow << '\n';
    return 0;
}