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

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 maxflow=0;
int direction[1005],delta[1005],parent[1005];

queue<int> R;
int visited[1005];

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];
        }
    }

    R.push(s);
    delta[s] = INT_MAX;
    visited[s]=1;


    while(R.empty() == 0)
    {
        current = R.front();
        R.pop();
            for(int i=1;i<=n;i++)
            {
                if(capacity[current][i] - flow[current][i] > 0 && visited[i] == 0)
                {
                    R.push(i);
                    delta[i] = min(delta[current], capacity[current][i] - flow[current][i]);
                    direction[i] = 1;
                    parent[i] = current;
                    visited[i] = 1;
                }
                if(flow[i][current] > 0 && visited[i] == 0)
                {
                    R.push(i);
                    delta[i] = min(delta[current], flow[i][current]);
                    direction[i] = -1;
                    parent[i] =current;
                    visited[i] = 1;
                }
            }
        if(visited[t] == 1)
        {
            v = t;
            maxflow+=delta[t];
            while(parent[v] != 0)
            {
                if(direction[v] == 1)
                {
                    flow[parent[v]][v] += delta[t];
                }
                else
                {
                    flow[parent[v]][v] -= delta[t];
                }
                v=parent[v];
            }
            for(int i=1;i<=n;i++) visited[i] = 0;
            visited[s] = 1;
            queue <int> empty;
            swap(R,empty);
            R.push(s);
        }
    }

    /*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;


    return 0;
}