#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#include <cstdlib>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int s,t;
int n,m;
int u,v;
int current;
int capacity[1005][1005];
int flow[1005][1005];
int rezidual[1005][1005];
int maxflow=0;
int visited[1005],delta[1005],parent[1005];

bool bfs(int s, int t)
{
    queue <int> q;
    q.push(s);
    for(int i=1;i<=n;i++) visited[i] =0;
    visited[s] = 1;
    int current;
    delta[s] = INT_MAX;

    while(q.empty() == 0)
    {
        current = q.front();
        q.pop();

        for(int i=1;i<=n;i++)
        {
            if(rezidual[current][i] > 0 && visited[i] == 0)
            {
                visited[i] = 1;
                parent[i] = current;
                delta[i] = min(delta[current], rezidual[current][i]);
                if(i == t) { return true; }
                q.push(i);
            }
        }

    }
    return false;
}


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

    s=1;
    t=n;

    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            fin >> u >> v;
            fin >> capacity[u][v];
            rezidual[u][v] = capacity[u][v];
            //cout << u << v << capacity[u][v];
        }
    }

    while(true)
    {
        //cout << "hey" << endl;
        if(!bfs(s,t)) break;

        u = t;
        maxflow+=delta[t];
        while(parent[u] != 0)
        {
            rezidual[parent[u]][u] -= delta[t];
            rezidual[u][parent[u]] += delta[t];
            flow[parent[u]][u] += delta[t];
            if(capacity[u][parent[u]] > 0) flow[u][parent[u]] -= delta[t];
            u = parent[u] ;
        }

    }

    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout << flow[i][j] << " ";
        }
        cout << endl;
    }

    cout << "Maxflow : " << maxflow <<endl;*/
    fout << maxflow << endl;


    return 0;
}