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

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

int varfuri, muchii, start, final, C[1005][1005], F[1005][1005], viz[1005], L[1005];
vector<int> G[1005];

int main()
{
    fin >> varfuri >> muchii;
    start = 1;
    final = varfuri;
    for (int i = 1; i <= muchii; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        C[x][y] = c;
        G[x].push_back(y);
    }
    do
    {
        for (int i = 1; i <= varfuri; ++i)
            viz[i] = 0;

        queue<int> qu;
        qu.push(start);
        viz[start] = 1;
        while (!(qu.empty() || viz[final]))
        {
            int elem = qu.front();
            qu.pop();
            for (int i = 0; i < G[elem].size(); ++i)
                if (!viz[G[elem][i]])
                {
                    if (F[elem][G[elem][i]] < C[elem][G[elem][i]])
                    {
                        viz[G[elem][i]] = elem;
                        qu.push(G[elem][i]);
                    }
                    else if (F[G[elem][i]][elem] > 0)
                    {
                        viz[G[elem][i]] = - elem;
                        qu.push(G[elem][i]);
                    }
                }
        }
        if (!viz[final])
            break;

        L[0] = final;
        int lant = 0, a, b, v;
        a = b = 1 << 30;
        while (L[lant] != start)
        {
            L[++lant] = abs(viz[L[lant-1]]);
            if (viz[L[lant-1]] > 0)
                a = min(a, C[L[lant]][L[lant-1]] - F[L[lant]][L[lant-1]]);
            else if (viz[L[lant-1]] < 0)
                b = min(b, F[L[lant-1]][L[lant]]);
        }
        v = min(a, b);
        for (int i = lant; i >= 1; --i)
            if (viz[L[i-1]] > 0)
                F[L[i]][L[i-1]] += v;
            else
                F[L[i-1]][L[i]] -= v;
    } while (1);

    /*for (int i = 1; i <= varfuri; ++i)
        for (int j = 1; j <= varfuri; ++j)
            if (F[i][j])
                fout << i << '-' << j << " : " << F[i][j] << '\n';*/
    int fmax = 0;
    for (int i = 1; i <= varfuri; ++i)
        fmax += F[i][final];
    fout << fmax;
}