/**
   Algoritmul lui Dinic:
   - cauta la fiecare BFS un numar maximal (nu maxim!) de drumuri de crestere
   Complexitate teoretica O(n x n x m)
   Complexitate practica: tinde la O(n x m)
*/

#include <bits/stdc++.h>
#define nmax 1001
#define oo 1000000000

using namespace std;

int n, m, S, D;
int c[nmax][nmax]; /// c[i,j]=capacitatea de transport a muchiei ij
int f[nmax][nmax]; /// f[i,j]=fluxul de pe muchia ij
int t[nmax];       /// t[i]=nodul precendent din drumul de crestere de la S la i
int flux;
vector<int> L[nmax];

void Citire()
{
    int i, x, y, cost;
    ifstream fin("maxflow.in");
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        c[x][y] = cost;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    S = 1; D = n;
    fin.close();
}

/// returneaza 1 daca exista drum de crestere de la s la d
int BFS(int s, int d)
{
    int pr, ul, nod, q[nmax];
    memset(t, 0, sizeof(t));
    pr = ul = 0;
    q[pr] = s;
    t[s] = -1;
    while (pr <= ul)
    {
        nod = q[pr++];
        for (auto i : L[nod])
            if (t[i] == 0 && c[nod][i] > f[nod][i])
            {
                q[++ul] = i;
                t[i] = nod;
            }
    }
    if (t[d] != 0) return 1;
    return 0;
}

void Dinic()
{
    int i, j, r;
    for (flux = 0; BFS(S, D); )
        for (i = 1; i <= n; i++)
        {
            if (t[i] == -1 || c[i][D] <= f[i][D]) continue;
            r = c[i][D] - f[i][D];
            for (j = i; j != S && j > 0; j = t[j])
                r = min(r, c[t[j]][j] - f[t[j]][j]);
            if (r == 0) continue;
            f[i][D] += r;
            f[D][i] -= r;
            for (j = i; j != S; j = t[j])
            {
                f[t[j]][j] += r;
                f[j][t[j]] -= r;
            }
            flux += r;
        }
}

void Afisare()
{
    ofstream fout("maxflow.out");
    fout << flux << "\n";
    fout.close();
}

int main()
{
    Citire();
    Dinic();
    Afisare();
    return 0;
}