#include <bits/stdc++.h>

using namespace std;
int flux[1001][1001], capacitate[1001][1001];
deque <int> sol;
int tata[1001];
int viz[1001];
int n;
vector <int> graf[1001];
vector <int> vecinii_n;
bool maxflow (int nod)
{
    sol.push_back(nod);
    viz[nod] = 1;
    while (!sol.empty())
    {
        int node = sol.front();
        sol.pop_front();
        for (auto x:graf[node])
        {
            if (capacitate[node][x]>flux[node][x] && viz[x]==0)
            {
                tata[x] = node;
                viz[x] = 1;
                sol.push_back(x);
            }
        }
    }
    return viz[n];
}
int main()
{
    ifstream fin ("maxflow.in");
    ofstream fout ("maxflow.out");
    int m, fluxul = 0;
    fin >> n >> m;
    for (int i = 1; i<=m; ++i)
    {
        int x, y, cap;
        fin >> x >> y >> cap;
        graf[x].push_back(y);
        capacitate[x][y] += cap;
        if (y == n)
            vecinii_n.push_back(x);
    }
    for (; maxflow(1);)
    {
        for (auto x:vecinii_n)
        {
            if (viz[x]==1 && capacitate[x][n]>flux[x][n])
            {
                int minim = capacitate[x][n]-flux[x][n];
                int copie = x;
                while (copie!=1)
                {
                    if (minim > capacitate[tata[copie]][copie]-flux[tata[copie]][copie])
                        minim = capacitate[tata[copie]][copie]-flux[tata[copie]][copie];
                    copie = tata[copie];
                }
                fluxul+=minim;
                copie = x;
                flux[x][n]+=minim;
                flux[n][x]-=minim;
                while (copie!=1)
                {
                    flux[tata[copie]][copie]+=minim;
                    flux[copie][tata[copie]]-=minim;
                    copie = tata[copie];
                }
            }
        }
        memset(tata, 0, sizeof(tata));
        memset(viz, 0, sizeof(viz));
    }
    fout << fluxul;
    return 0;
}