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

/**
 * @brief Structura folosita pentru a stoca daca exista
 * drum de ameliorare / cale reziduala (drum de la sursa la trena)
 * si care este acesta.
 */
struct AugmentedPath {
    bool hasPath;
    vector<pair<int, int>> path;

    AugmentedPath(bool _hasPath, const vector<pair<int, int>>& _path)
        : hasPath(_hasPath)
        , path(_path) { }

    operator bool() const {
        return hasPath;
    }
};

class Task {
 public:
    void solve() {
        read_input();
        print_output(get_result());
    }

 private:
    int n, m;

    vector<vector<int>> adj;
    vector<vector<int>> cap;

    void read_input() {
        ifstream fin("maxflow.in");
        fin >> n >> m;

        cap.resize(n + 1, vector<int>(n + 1, 0));
        adj.resize(n + 1);

        for (int i = 0, x, y, capacity; i < m; i++) {
            fin >> x >> y >> capacity;
            
            adj[x].push_back(y);
            adj[y].push_back(x);

            cap[x][y] += capacity;
        }

        fin.close();
    }

    int get_result() {
        return get_maxflow(n + 1, 1, n);
    }

    int get_maxflow(int nodes, int source, int sink) {
        int total_flow = 0;
        vector<vector<int>> flow(nodes + 1, vector<int>(nodes + 1, 0));

        while (auto res = bfs(nodes, source, sink, flow)) {
            auto& [_, path] = res;

            int minFluxPath = INT32_MAX;
            // Calculare flux min (ca sa satisfaca capac fiecarui arc)
            // pentru drumul de ameliorare
            for (auto& [u, v] : path) {
                minFluxPath = min(minFluxPath, cap[u][v] - flow[u][v]);
            }

            total_flow += minFluxPath;
            for (auto& [u, v] : path) {
                flow[u][v] += minFluxPath;
                flow[v][u] -= minFluxPath;
            }
        }

        return total_flow;
    }

    AugmentedPath bfs(int nodes, int source, int sink, vector<vector<int>>& flow) {
        vector<int> p(nodes, -1);
        queue<int> q;

        q.push(source);
        p[source] = 0;

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (auto& neigh : adj[node]) {
                if (p[neigh] == -1 && flow[node][neigh] < cap[node][neigh]) {
                    p[neigh] = node;
                    q.push(neigh);
                }
            }
        }

        if (p[sink] == -1) {
            return {false, {}};
        }

        vector<pair<int, int>> path;
        int node = sink;

        while (p[node] != 0) {
            path.push_back({p[node], node});
            node = p[node];
        }

        reverse(path.begin(), path.end());
        return {true, path};
    }

    void print_output(int result) {
        ofstream fout("maxflow.out");
        fout << result << '\n';
        fout.close();
    }
};

int main() {
    auto* task = new (nothrow) Task();

    if (!task) {
        cerr << "new failed!\n";
        return -1;
    }

    task->solve();
    delete task;

    return 0;
}