#include <bits/stdc++.h>
#define ll long long 

using namespace std;

const int NMAX = 5003;
const ll INF = 1e15;

int n, m, source, sink;
ll capacity[NMAX][NMAX];
ll flow[NMAX][NMAX];
vector<ll> excess, height, next_son;
queue<int> excess_vertexes;

void relabel(int u) {
    ll d = INF;
    for(int i = 1; i <= n; i++) {
        if(capacity[u][i] > flow[u][i]) {
            d = min(d, height[i]);
        }
    }
    if(d < INF) {
        height[u] = d + 1;
    }
}

// The the flow from node u to node v
void push(int u, int v) {
    // How much flow does the edge support
    ll d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if(d && excess[v] == d) {
        excess_vertexes.push(v);
    }
}

void discharge(int u) {
    while(excess[u] > 0) {
        if(next_son[u] <= n) {
            int v = next_son[u];
            if(capacity[u][v] - flow[u][v] > 0 && height[u] > height[v]) {
                push(u, v);
            } else {
                next_son[u]++;
            }
        } else {
            relabel(u);
            next_son[u] = 1;
        }
    }
}

int main() {
    ifstream in("maxflow.in");
    ofstream out("maxflow.out");
    in >> n >> m;

    source = 1, sink = n;
    excess.resize(n+1);
    height.resize(n+1);
    next_son.resize(n+1);

    height[source] = n;
    excess[source] = INF;

    for(int i = 1; i <= m; i++) {
        int x, y, cap;
        in >> x >> y >> cap;
        capacity[x][y] += cap;
    }

    for(int i = 1; i <= n; i++) {
        if(i == source) continue;
        push(source, i);
    }

    while(!excess_vertexes.empty()) {
        int node = excess_vertexes.front();
        excess_vertexes.pop();
        if(node != source && node != sink) {
            discharge(node);
        }
    }

    ll max_flow = 0;
    for(int node = 1; node <= n; node++) {
        max_flow += flow[node][sink];
    }

    out << max_flow << '\n';

    return 0;
}