// Ferencz Peter 512/1 fpim2346
// image segmentation

#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

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

/*void read(vector<vector<int> >& adj, int& n)
{
    fin >> n;
    adj.resize(n + 1, vector<int>(n + 1));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            fin >> adj[i][j];
        }
    }
}*/

void read(vector<vector<int> >& adj, int& n, int& m)
{
    fin >> n >> m;
    adj.resize(n + 1, vector<int>(n + 1));
    int x, y, w;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> w;
        adj[x-1][y-1] = w;
    }
}

int min(int a, int b)
{
    if (a > b)
        return b;
    return a;
}

//checks if there is path between s (source) and t (sink) nodes
//fills the parent array with the found path
bool bfs(int s, int t, vector<vector<int> > &adj, vector<int> &parent, int n) {
    parent[s] = -1;
    
    vector<bool>vis(n + 1, false);
    queue<int> q;
    vis[s] = true;
    q.push(s);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int i = 0; i < n; i++) {
            if (!vis[i] && adj[node][i]) {
                q.push(i);
                vis[i] = true;
                parent[i] = node;

                //if the node is the sink, than we found a path
                if (i == t)
                {
                    return true;
                }
            }
        }
    }

    //if there is no path between s and t
    return false;
}

//Ford Fulkerson algorithm
int maxFlow(vector<vector<int> > &adj, int s, int t, int n)
{
    int max_fl = 0;

    int start, end;
    vector<vector<int> > resGraph(n + 1, vector<int>(n+1));

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            resGraph[i][j] = adj[i][j];
        }
    }

    vector<int> parent(n + 1);

    while (bfs(s, t, resGraph, parent, n))
    {
        //finds the maximum flow on the path found by the bfs
        int max_pt_flow = INT_MAX;
        int i = t;
        int j;
        while (i != s)
        {
            j = parent[i];
            max_pt_flow = min(max_pt_flow, resGraph[j][i]);
            i = parent[i];
        }

        //after we found the maximum possiple flow on the path we need to update the residual matrix
        i = t;
        while (i != s)
        {
            j = parent[i];
            resGraph[j][i] -= max_pt_flow;
            resGraph[i][j] += max_pt_flow;
            i = parent[i];
        }

        max_fl += max_pt_flow;
    }
    return max_fl;
}


int main()
{
    int n, m;
    vector<vector<int> >adj;
    read(adj, n, m);

    fout << maxFlow(adj, 0, n-1, n);

    return 0;
}