#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int inf = 1000000000;

int n, m, x, y, z;
vector<vector<int>> capacity, flow;
vector<int> height, excess;

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
}

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

vector<int> find_max_height_vertices(int s, int t) {
    vector<int> max_height;
    for (int i = 0; i < n; i++) {
        if (i != s && i != t && excess[i] > 0) {
            if (!max_height.empty() && height[i] > height[max_height[0]])
                max_height.clear();
            if (max_height.empty() || height[i] == height[max_height[0]])
                max_height.push_back(i);
        }
    }
    return max_height;
}

int max_flow(int s, int t)
{
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
        if (i != s)
            push(s, i);
    }

    vector<int> current;
    while (!(current = find_max_height_vertices(s, t)).empty()) {
        for (int i : current) {
            bool pushed = false;
            for (int j = 0; j < n && excess[i]; j++) {
                if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1) {
                    push(i, j);
                    pushed = true;
                }
            }
            if (!pushed) {
                relabel(i);
                break;
            }
        }
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

int main() {
    in >> n >> m;
    capacity.assign(n, vector<int>(n, 0));
    for(int i = 1; i <= m; i++){
        in >> x >> y >> z;
        capacity[x - 1][y - 1] = z;
    }
    out << max_flow(0, n - 1) << '\n';
    //min-cut intre nodurile 0 si n - 1
//    viz.assign(n, 0);
//    x = 0;
//    y = n - 1;
//    out << "Min-cut: " << max_flow(x, y) << '\n';
//    out << "Edges set: ";
//    DFS(x);
//    for(auto& nod : vertices_set){
//        for(int i = 0; i < n; i++){
//            if(capacity[nod][i] > 0)
//                out << nod << " - " << i << '\n';
//        }
//    }
    return 0;
}