#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

std::ifstream in("maxflow.in");
std::ofstream out("maxflow.out");

const int nmax = 1001;
const int inf = 1e9 + 10;

int n, m;

int ca[nmax][nmax], f[nmax][nmax];
int h[nmax], e[nmax], p[nmax];

std::vector<int> MH;

void push(int u, int v)
{
    long long rr = std::min(e[u], ca[u][v] - f[u][v]);
    f[u][v] += rr;
    f[v][u] -= rr;
    e[u] -= rr;
    e[v] += rr;
}
void relabel(int u)
{
    int r = inf;
    for ( int i = 1; i <= n; ++i )
        if ( ca[u][i] - f[u][i] > 0 )
           r = std::min(r, h[i]);
    if ( r < inf )
       h[u] = r + 1;
}

void GetMH(int s, int t)
{
    MH.clear();
    for ( int i =1; i <= n; ++i )
       if ( i != s and i != t and e[i] ){
         if ( !MH.empty() and h[i] > h[MH[0]] )
            MH.clear();
         if ( MH.empty() || h[i] == h[MH[0]] )
            MH.emplace_back(i);
       }
}

void dispatch(int u)
{
    while ( e[u] )
        if ( p[u] <= n )
        {
            int v = p[u];
            if ( ca[u][v] - f[u][v] > 0 and h[u] == h[v] + 1)
                push(u, v);
            else p[u]++;
        }
        else
        {
            p[u] = 1;
            relabel(u);
        }
}

long long fl(int s, int t)
{
    long long flo = 0;
    e[s] = inf;
    h[s] = n;
    for ( int i = 1; i <= n; ++i )
       push(s, i);
    while ( (GetMH(s, t), !MH.empty()) )
        for ( auto c : MH )
           dispatch(c);

    for ( int i = 1; i <= n; ++i )
        flo += f[s][i];
    return flo;
}

int main()
{
    in >> n >> m;

    int a, b, c;
    for ( int i = 1; i <= m; ++i )
    {
        in >> a >> b >> c;
        ca[a][b] = c;
    }

    for ( int i = 0; i <= n; ++i )
        p[i] = 1, h[i] = 0;
    out << fl(1, n);
    return 0;
}