#include<fstream>
#include<vector>
using namespace std;
#define INF 2000000000
#define pb push_back
#define nmax 1005

vector<int> G[nmax];
int viz[nmax], C[nmax][nmax], F[nmax][nmax], q[nmax], ante[nmax];
int N,M;

void citire ()
{
	int i,x,y,z;
    ifstream fin("maxflow.in");
    fin >> N >> M;
    for(i = 1;i <= M; ++i)
    {
        fin >> x >> y >> z;
        G[x].pb(y);
        G[y].pb(x);
        C[x][y] += z;
        F[x][y] = F[y][x] = 0;
    }
}

bool BFS()
{   vector<int>::iterator it;
    int u;
    memset(q, 0, sizeof(q));
    memset(viz, 0, sizeof(viz));
    int front = 1;
    viz[1] = 1;
    q[++q[0]] = 1;
    while(front <= q[0])
    {
        u = q[front++];
        for(it = G[u].begin(); it < G[u].end(); ++it)
        {
            if( !viz[*it] && C[u][*it] > F[u][*it])
            {
                viz[*it] = 1;
                ante[*it] = u;
                q[++q[0]] = *it;
            }
        }
    }
    return viz[N];
}

void solve ()
{
    int i, fmin, flow;
    vector<int>::iterator it;
    for(flow = 0; BFS();)
    {
        fmin = INF;
        for(it = G[N].begin(); it < G[N].end(); ++it)
        if(viz[*it] && C[*it][N] > 0)
        {
            fmin = C[*it][N] - F[*it][N];
            for(i = *it; i > 1; i = ante[i])
            {
                fmin = min(fmin, C[ante[i]][i] - F[ante[i]][i]);
            }
            F[*it][N] += fmin;
            F[N][*it] -= fmin;
            for(i = *it; i != 1; i = ante[i])
            {
                F[ante[i]][i] += fmin;
                F[i][ante[i]] -= fmin;
            }
            flow += fmin;
        }
    }
	ofstream fout("maxflow.out");
    fout << flow << "\n";
}

int main()
{
    citire ();
    solve ();
    return 0;
}