#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

vector<int> g[1001];
int c[1001][1001], f[1001][1001], t[1001], flux, S, D;

int bfs()
{
    int ok = 0;
    queue<int> q;
    memset(t,0,sizeof(t));

    t[S] = -1;
    q.push(S);

    for(int nod; !q.empty(); q.pop())
    {
        nod = q.front();

        for(vector<int>::iterator it = g[nod].begin(); it!= g[nod].end(); ++it)
            if(t[*it]==0 && c[nod][*it] > f[nod][*it])
        {
            if(*it != D)
            {
                t[*it] = nod;
                q.push(*it);
            }
            else ok = 1;
        }
    }

    return ok;
}

void dinic()
{
    for(int drum = bfs(); drum; drum = bfs())
        for(vector<int>::iterator it = g[D].begin(); it != g[D].end(); ++it)
            if(t[*it] && c[*it][D]>f[*it][D])
        {
            t[D] = *it;
            int mini = 0x7fffffff;

            for(int nod = D; nod != S; nod = t[nod])
                if(mini>c[t[nod]][nod]-f[t[nod]][nod])
                    mini = c[t[nod]][nod]-f[t[nod]][nod];

            if(mini<=0)
                continue;

            flux += mini;

            for(int nod = D; nod != S; nod = t[nod])
            {
                f[t[nod]][nod] += mini;
                f[nod][t[nod]] -= mini;
            }
        }
}

int main()
{
    int M,N,x,y;

    memset(c,0,sizeof(c));
    memset(f,0,sizeof(f));

    fin >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        fin >> x >> y;
        fin >> c[x][y];

        g[x].push_back(y);
        g[y].push_back(x);
    }

    S= 1;
    D = N;

    dinic();

    fout << flux;


    return 0;
}