#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

void read(int &n, vector<vector<int>> &G, vector<vector<int>> &GT,
          vector<vector<int>> &f, vector<vector<int>> &cost) {
    ifstream fin("maxflow.in");
    if (!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    int m;
    fin >> n >> m;
    G.resize(n + 1);
    GT.resize(n + 1);
    f.resize(n + 1);
    cost.resize(n + 1);

    //O(n^2)
    for (int i = 0 ; i <= n; ++i) {
        f[i].resize(n + 1, 0);
        cost[i].resize(n + 1, 0);
    }

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        G[x].emplace_back(y);
        GT[y].emplace_back(x);
        cost[x][y] = z;
    }

    fin.close();
}

bool BFS(int n, const vector<vector<int>> &G, const vector<vector<int>> &GT,
         const vector<vector<int>> &cost, const vector<vector<int>> &f, vector<int> &tata) {
    queue<int> Q;
    vector<int> viz(n + 1, 0);
    tata = vector<int>(n + 1, 0);

    Q.push(1);
    viz[1] = 1;
    while (!Q.empty()) {
        int u = Q.front();
        //cout << u << '\n';
        Q.pop();
        for (const auto &v : G[u]) {
            if (viz[v] == 0 && cost[u][v] - f[u][v] > 0) {
                Q.push(v);
                viz[v] = 1;
                tata[v] = u;
                if (v == n) {
                    return true;
                }
            }
        }
        for (const auto &v : GT[u]) {
            //cout << v << ' ' << u << '\n';
            if (viz[v] == 0 && f[v][u] > 0) {
                Q.push(v);
                viz[v] = 1;
                tata[v] = -u;
                if (v == n) {
                    return true;
                }
            }
        }

    }
    return false;
}

int main() {
    int n;
    vector<vector<int>> G, GT, f, cost;
    read(n, G, GT, f, cost);

    vector<int> tata;
    while (BFS(n, G, GT, cost, f, tata)) {
        //gaseste cantitatea reziduala
        int IP = 110005;
        int t = n;
        while (tata[t]) {
            if (tata[t] >= 0) {
                if (IP > cost[tata[t]][t] - f[tata[t]][t])
                    IP = cost[tata[t]][t] - f[tata[t]][t];
                t = tata[t];
            } else if (tata[t] < 0) {
                if (IP > f[t][-tata[t]])
                    IP = f[t][-tata[t]];
                t = -tata[t];
            }
        }

        //Revizuieste lant
        t = n;
        while (tata[t]) {
            if (tata[t] >= 0) {
                f[tata[t]][t] += IP;
                t = tata[t];
            } else if (tata[t] < 0) {
                f[t][-tata[t]] -= IP;
                t = -tata[t];
            }
        }
    }

    int flux = 0;
    for (const auto &it : G[1]) {
        flux += f[1][it];
    }

    ofstream fout("maxflow.out");
    fout << flux << '\n';
    return 0;
}