#include <iostream>
#include <fstream>
#include <queue>
#include <string.h>

using namespace std;

void print_path(int *parent, int i, int j) {
    if (i <= 0) return;
    print_path(parent, parent[i], i);
    cout<<i<<"->"<<j<<endl;
}

int main()
{
    ifstream in("maxflow.in");
    ofstream out("maxflow.out");
    int n, m;
    in>>n>>m;
    int S = 1;
    int D = n;

    int cap[n+1][n+1];
    int flw[n+1][n+1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {

            cap[i][j] = 0;
            flw[i][j] = 0;
        }
    int parent[n+1];
    queue<int> bfsq;
    int x, y;
    for (int i = 0; i < m; i++) {
        in>>x>>y;
        in>>cap[x][y];
    }

    while (true) {
        memset(parent, -1, (n+1) * sizeof(int));
        //BFS
        bfsq.push(S);
        parent[S] = 0;
        while (!bfsq.empty()) {
            int i = bfsq.front();
            bfsq.pop();
            for (int j = 1; j <= n; j++)
                if ((parent[j] < 0) && (cap[i][j] > flw[i][j])) {
                    bfsq.push(j);
                    parent[j] = i;
                }
        }
        //stop when we can't found path from S to D
        if (parent[D] == -1) break;


        int max_fl_inc = 999999;
        //find maximum flow increase amount for current S->D path
        {
            int i = parent[D], j = D;
            while (i > 0) {
                max_fl_inc = min(max_fl_inc, cap[i][j] - flw[i][j]);
                j = i;
                i = parent[i];
            }
        }
        //increase flow on every path's edge by max_fl_inc
        {
            int i = parent[D], j = D;
//            cout<<"increasing flow on the path below by "<<max_fl_inc<<endl;
//            print_path(parent, i, j);
            while (i > 0) {
                flw[i][j] += max_fl_inc;
                j = i;
                i = parent[i];
                flw[j][i] -= max_fl_inc;
            }
        }
    }
    int flow = 0;
    for (int j = 1; j <= n; j++)
        flow += flw[S][j];
    out<<flow<<endl;

//    cout<<"Max Flow = "<<flow;
    return 0;
}