#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pii;
const int inf = 1 << 30;

template<typename T>
class Graph {
public:
    // constructori
    Graph() : m_n(0), m_ad(), m_tAd() {}

    Graph(int n, vector<vector<T>> &ad) :
            m_n(n), m_ad(ad), m_tAd() {}

    Graph(int n, vector<vector<T>> &ad, vector<vector<T>> &tAd) :
            m_n(n), m_ad(ad), m_tAd(tAd) {}

    // dfs
    void DFS(int v, vector<bool> &vis) {
        vis[v] = true;

        for (auto &x : m_ad[v]) {
            if (!vis[x]) {
                DFS(x, vis);
            }
        }
    }

    int components() {
        int compCount = 0;
        vector<bool> vis(m_n, false);

        for (int i = 1; i <= m_n; ++i) {
            if (!vis[i]) {
                ++compCount;
                DFS(i, vis);
            }
        }

        return compCount;
    }

    // bfs
    void minDist(int start, ostream &out) {
        vector<int> dist(m_n + 1, -1);
        queue<int> Q;
        int x;

        dist[start] = 0;
        Q.push(start);

        while (!Q.empty()) {
            x = Q.front(); Q.pop();

            for (auto &y : m_ad[x]) {
                if (dist[y] == -1) {
                    dist[y] = dist[x] + 1;
                    Q.push(y);
                }
            }
        }

        for (int i = 1; i <= m_n; ++i) {
            out << dist[i] << ' ';
        }
    }

    // sortare topologica
    void topologicalSort(int v, vector<bool> &vis, vector<int> &stack) {
        vis[v] = true;

        for (auto &x : m_ad[v]) {
            if (!vis[x]) {
                topologicalSort(x, vis, stack);
            }
        }

        stack.push_back(v);
    }

    void printTopoSorted(ostream &out) {
        vector<bool> vis(m_n + 1, false);
        vector<int> stack;

        for (int i = 1; i <= m_n; ++i) {
            if (!vis[i]) {
                topologicalSort(i, vis, stack);
            }
        }

        for (auto i = stack.size() - 1; i >= 0; --i) {
            out << stack[i] << ' ';
        }
    }

    // ctc
    void tDFS(int v, vector<bool> &vis, int compCount, vector<vector<int>> &comp) {
        vis[v] = true;
        comp[compCount - 1].push_back(v);

        for (auto &x : m_tAd[v]) {
            if (!vis[x]) {
                tDFS(x, vis, compCount, comp);
            }
        }
    }

    void stronglyConnectedComponents(ostream &out) {
        vector<bool> vis1(m_n + 1, false);
        vector<bool> vis2(m_n + 1, false);
        vector<int> stack;
        int compCount = 0;
        vector<vector<int>> comp;

        for (int i = 1; i <= m_n; ++i) {
            if (!vis1[i]) {
                topologicalSort(i, vis1, stack);
            }
        }

        for (auto i = stack.size() - 1; i >= 0; --i) {
            if (!vis2[stack[i]]) {
                ++compCount;
                comp.emplace_back();
                tDFS(stack[i], vis2, compCount, comp);
            }
        }

        out << compCount << '\n';

        for (int i = 0; i < compCount; ++i) {
            for (auto &x : comp[i]) {
                out << x << ' ';
            }

            out << '\n';
        }
    }

    // biconex
    void bccDFS(int v, int parent, vector<int> &disc, vector<int> &low,
                vector<int> &stack, vector<vector<int>> &comp) {
        static int time = 0;
        int children = 0;

        disc[v] = low[v] = ++time;

        for (auto &w : m_ad[v]) {
            if (w == parent) continue;

            if (!disc[w]) {
                ++children;
                stack.push_back(w);
                bccDFS(w, v, disc, low, stack, comp);
                low[v] = min(low[v], low[w]);

                if (low[w] >= disc[v]) {
                    comp.emplace_back();
                    stack.push_back(v);

                    while (!stack.empty() && stack.back() != w) {
                        comp[comp.size() - 1].push_back(stack.back());
                        stack.pop_back();
                    }

                    if (!stack.empty()) {
                        comp[comp.size() - 1].push_back(stack.back());
                        stack.pop_back();
                    }
                }
            } else if (w != parent) {
                low[v] = min(low[v], disc[w]);
            }
        }
    }

    void biconnectedComponents(ostream &out) {
        vector<int> disc(m_n + 1, 0);
        vector<int> low(m_n + 1, 0);
        vector<int> stack;
        vector<vector<int>> comp;

        bccDFS(1, 0, disc, low, stack, comp);

        out << comp.size() << '\n';

        for (auto &c : comp) {
            for (auto &v : c) {
                out << v << ' ';
            }

            out << '\n';
        }
    }

    // Havel Hakimi
    static bool eligible(vector<int> &v) {
        int s = 0;
        auto n = v.size();

        for (auto &x : v) {
            if (x > n - 1) {
                return false;
            }

            s += x;
        }

        return s % 2 == 0;
    }

    static string canBuildGraph(vector<int> &v) {
        if (!eligible(v)) {
            return "No";
        }

        sort(v.begin(), v.end(), greater<>());

        while (v[0]) {
            for (int i = 1; i <= v[0]; ++i) {
                if (v[i] == 0) {
                    return "No";
                }

                --v[i];
            }

            v.erase(v.begin());
            sort(v.begin(), v.end(), greater<>());
        }

        return "Yes";
    }

    // graf
    void findPaths(vector<vector<int>> &paths, vector<int> &path, vector<vector<int>> &parent, int current) {
        if (current == -1) {
            paths.push_back(path);
            return;
        }

        for (auto &p : parent[current]) {
            path.push_back(current);
            findPaths(paths, path, parent, p);
            path.pop_back();
        }
    }

    void BFS(vector<vector<int>> &parents, int start) {
        vector<int> dist(m_n + 1, inf);
        queue<int> Q;

        Q.push(start);
        parents[start] = {-1};
        dist[start] = 0;

        while (!Q.empty()) {
            int current = Q.front(); Q.pop();

            for (auto &x : m_ad[current]) {
                if (dist[current] + 1 < dist[x]) {
                    dist[x] = dist[current] + 1;
                    Q.push(x);

                    parents[x].clear();
                    parents[x].push_back(current);
                } else if (dist[x] == dist[current] + 1) {
                    parents[x].push_back(current);
                }
            }
        }
    }

    void optimalPaths(int start, int end, ostream &out) {
        vector<vector<int>> paths;
        vector<int> path;
        vector<vector<int>> parents(m_n + 1);

        BFS(parents, start);
        findPaths(paths, path, parents, end);

        vector<int> check(m_n + 1, 0);
        auto pathCount = paths.size();
        int count = 0;

        for (auto &p : paths) {
            for (auto &v : p) {
                ++check[v];
            }
        }

        for (int i = 1; i <= m_n; ++i) {
            if (check[i] == pathCount) {
                ++count;
            }
        }

        out << count << '\n';

        for (int i = 1; i <= m_n; ++i) {
            if (check[i] == pathCount) {
                out << i << ' ';
            }
        }
    }

    // disjoint
    int find(int x, vector<int> &root) {
        int rx = x, aux;

        while (rx != root[rx]) {
            rx = root[rx];
        }

        while (x != root[x]) {
            aux = root[x];
            root[x] = rx;
            x = aux;
        }

        return rx;
    }

    void unite(int x, int y, vector<int> &root, vector<int> &size) {
        int rx = find(x, root);
        int ry = find(y, root);

        if (size[rx] > size[ry]) {
            root[ry] = rx;
            size[rx] += size[ry];
        } else {
            root[rx] = ry;
            size[ry] += size[rx];
        }
    }

    void disjoint(int n, vector<pair<int, pair<int, int>>> &ops, ostream &out) {
        vector<int> root(n + 1);
        vector<int> size(n + 1, 1);

        for (int i = 1; i <= n; ++i) {
            root[i] = i;
        }

        for (auto &op : ops) {
            if (op.first == 1) {
                unite(op.second.first, op.second.second, root, size);
            } else {
                if (find(op.second.first, root) == find(op.second.second, root)) {
                    out << "DA\n";
                } else {
                    out << "NU\n";
                }
            }
        }
    }

    // dijkstra
    void dijkstra(ostream &out) {
        vector<int> dist(m_n + 1, inf);
        vector<bool> vis(m_n + 1, false);
        priority_queue<pii, vector<pii>, greater<pii>> heap;

        dist[1] = 0;
        heap.push({0, 1});

        while (!heap.empty()) {
            int current = heap.top().second;
            heap.pop();

            if (!vis[current]) {
                vis[current] = true;

                for (auto &w : m_ad[current]) {
                    if (dist[current] + w.second < dist[w.first]) {
                        dist[w.first] = dist[current] + w.second;
                        heap.push({dist[w.first], w.first});
                    }
                }
            }
        }

        for (int i = 2; i <= m_n; ++i) {
            if (dist[i] != inf) {
                out << dist[i] << ' ';
            } else {
                out << "0 ";
            }
        }
    }

    // bellman-ford
    void bellmanFord(ostream &out) {
        vector<int> dist(m_n + 1, inf);
        vector<bool> inHeap(m_n + 1, false);
        vector<int> count(m_n + 1, 0);
        priority_queue<pii, vector<pii>, greater<pii>> heap;
        bool foundCycle = false;

        dist[1] = 0;
        inHeap[1] = true;
        heap.push({0, 1});

        while (!heap.empty() && !foundCycle) {
            int current = heap.top().second;
            heap.pop();

            inHeap[current] = false;

            for (auto &w : m_ad[current]) {
                if (dist[current] + w.second < dist[w.first]) {
                    if (!inHeap[w.first]) {
                        ++count[w.first];
                        inHeap[w.first] = true;

                        heap.push({dist[w.first], w.first});

                        if (count[w.first] > m_n) {
                            foundCycle = true;
                        }
                    }

                    dist[w.first] = dist[current] + w.second;
                }
            }
        }

        if (foundCycle) {
            out << "Ciclu negativ!";
            return;
        }

        for (int i = 2; i <= m_n; ++i) {
            if (dist[i] != inf) {
                out << dist[i] << ' ';
            } else {
                out << "0 ";
            }
        }
    }

    // maxflow
    bool foundPath(vector<vector<int>> &c, vector<vector<int>> &flow, vector<int> &parent) {
        queue<int> Q;
        vector<bool> vis(m_n + 1, false);

        parent[1] = -1;
        Q.push(1);

        while (!Q.empty()) {
            int current = Q.front(); Q.pop();
            vis[current] = true;

            if (current == m_n) {
                continue;
            }

            for (auto &w : m_ad[current]) {
                if (!vis[w] && c[current][w] - flow[current][w]) {
                    parent[w] = current;
                    Q.push(w);
                }
            }
        }

        return vis[m_n];
    }

    int getMaxFlow(vector<vector<int>> &c) {
        int maxFlow = 0;
        vector<int> parent(m_n + 1);
        vector<vector<int>> flow(m_n + 1);

        for (int i = 1; i <= m_n; ++i) {
            flow[i].resize(m_n + 1, 0);
        }

        while (foundPath(c, flow, parent)) {
            for (auto &w : m_ad[m_n]) {
                int minFlow = c[w][m_n] - flow[w][m_n];

                for (int v = w; v != 1; v = parent[v]) {
                    minFlow = min(minFlow, c[parent[v]][v] - flow[parent[v]][v]);
                }

                if (minFlow == 0) {
                    continue;
                }

                flow[w][m_n] += minFlow;
                flow[m_n][w] -= minFlow;

                for (int v = w; v != 1; v = parent[v]) {
                    flow[parent[v]][v] += minFlow;
                    flow[v][parent[v]] -= minFlow;
                }

                maxFlow += minFlow;
            }
        }

        return maxFlow;
    }

private:
    int m_n;
    vector<vector<T>> m_ad;
    vector<vector<T>> m_tAd;
};

int main() {
    int n, m, x, y, z;

    fin >> n >> m;

    vector<vector<int>> ad(n + 1);
    vector<vector<int>> c(n + 1);

    for (int i = 1; i <= n; ++i) {
        c[i].resize(n + 1, 0);
    }

    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> z;

        ad[x].push_back(y);
        ad[y].push_back(x);
        c[x][y] += z;
    }

    Graph<int> G(n, ad);

    fout << G.getMaxFlow(c);

    return 0;
}