#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
const int inf = 1e9;

struct edge
{
    int u, v, cap, flow;
};

struct Dinic
{
    vector<edge> edg;
    vector<vector<int>> g;
    vector<int> level;
    vector<int> next;
    int s, t;
    Dinic(int n, int s, int t) : s(s), t(t)
    {
        g.resize(n + 1);
        level.resize(n + 1);
        next.resize(n + 1);
    }
    void add_edge(int u, int v, int c)
    {
        int sz = edg.size();
        edg.push_back({u, v, c, 0});
        edg.push_back({v, u, 0, 0});
        g[u].push_back(sz);
        g[v].push_back(sz + 1);
    }
    bool bfs()
    {
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty())
        {
            int qui = q.front();
            q.pop();
            for (auto i : g[qui])
            {
                auto x = edg[i];
                if (x.cap == x.flow || level[x.v] != -1)
                {
                    continue;
                }
                level[x.v] = level[qui] + 1;
                q.push(x.v);
            }
        }
        return level[t] != -1;
    }
    int dfs(int node, int push)
    {
        if (node == t || push == 0)
        {
            return push;
        }
        for (int &i = next[node]; i < g[node].size(); ++i)
        {
            auto x = edg[g[node][i]];
            if (x.cap == x.flow || level[x.v] != level[node] + 1)
            {
                continue;
            }
            int flux = dfs(x.v, min(push, x.cap - x.flow));
            if (flux == 0)
            {
                continue;
            }
            edg[g[node][i]].flow += flux;
            edg[g[node][i] ^ 1].flow -= flux;
            return flux;
        }
        return 0;
    }
    int flow()
    {
        int ans = 0;
        while (true)
        {
            fill(level.begin(), level.end(), -1);
            fill(next.begin(), next.end(), 0);
            if (!bfs())
            {
                break;
            }
            while (int add = dfs(s, inf))
            {
                ans += add;
            }
        }
        return ans;
    }
};
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    fin >> n >> m;
    Dinic G(n, 1, n);
    for (int i = 1; i <= m; ++i)
    {
        int a, b, cost;
        fin >> a >> b >> cost;
        G.add_edge(a, b, cost);
    }
    fout << G.flow();
}