/*
	Mitoi Stefan - Daniel
	Grupa 231
	Fluxuri în reţele de transport - problema 1
*/

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

#define NMAX 100010
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

typedef struct {
    int capacity;
    int flow;
    int flow_r;
    int source;
    int sink;
} edge;

int n, m, s, t, a;
vector<edge> 	listaArce[NMAX];

int     edmonds_karp() {
    edge* pred[NMAX];
    int flow = 0;

    do {
        for (int i = 0; i <= n; i++)
            pred[i] = NULL;

        queue<int> q = queue<int>();
        q.push(s);
        while (q.empty() != true) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < listaArce[u].size(); i++) {
                edge e = listaArce[u][i];
                if (pred[e.sink] == NULL && e.sink != s && e.capacity > e.flow) {
                    pred[e.sink] = &listaArce[u][i];
                    // cout << e.sink << " = " << pred[e.sink] -> source << " -> " << pred[e.sink] -> sink << '\n';
                    q.push(e.sink);
                }
            }
        }
        // cout << "Trecut de BFS" << '\n';

        if (pred[t] != NULL) {
            int diff_flow = INF;

            for (edge* e = pred[t]; e != NULL; e = pred[e -> source]) {
                // cout << "Mers pe muchia " << e -> source << " -> " << e -> sink << '\t' << e -> flow << '/' << e -> capacity << '\n';
                diff_flow = min(diff_flow, e -> capacity - e -> flow);
            }

            for (edge* e = pred[t]; e != NULL; e = pred[e -> source]) {
                e -> flow += diff_flow;
                e -> flow_r -= diff_flow;
                // cout << "Adaugat " << diff_flow << " pe muchia " << e -> source << " -> " << e -> sink << '\t' << e -> flow << '/' << e -> capacity << '\n';
            }
            flow += diff_flow;
            // cout << "Flow = " << flow << '\n';
        }
    } while (pred[t] != NULL);

    return flow;
}


int		main()
{
	f >> n >> m;
    s = 1;
    t = n;
	// cout << "n = " << n << '\n';
    // cout << "s = " << s << '\n';
	// cout << "t = " << t << '\n';
	// cout << "m = " << m << '\n';

	for (int i = 0; i < m; i++) {
        int x, y, c, s;
        edge e;
        edge r;
        f >> x >> y >> c;
        e.capacity = c; e.flow = 0; e.sink = y; e.source = x; e.flow_r = s;
        listaArce[x].push_back(e);
        // cout << "Adaugat muchia " << x << " -> " << y << '\t' << s << '/' << c << '\n';
    }

    g << edmonds_karp();

	return 0;
}