#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
#define INT_MAX 2147483647;

using namespace std;

//1. algoritmul edmonds-karp

int n, m, maxFlow;
vector<vector<int>> adj, rez;
vector<int> anc;
vector<bool> viz;

//parcurgerea bfs care gaseste lanturi de la start la final:
bool bfs() {
    queue<int> q;
    anc.clear();
    anc.resize(n + 1, 0);
    viz.clear();
    viz.resize(n + 1, false);

    q.push(1);
    viz[1] = true;

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

        for (int i = 0; i < adj[curr].size(); i++) {
            if (!viz[adj[curr][i]] && rez[curr][adj[curr][i]] > 0) {
                anc[adj[curr][i]] = curr;
                q.push(adj[curr][i]);
                viz[adj[curr][i]] = true;
                
                if (adj[curr][i] == n)
                    return true;
            }
        }
    }

    return false;
}

//algoritmul edmonds-karp:
void edmondsKarp() {
    //cat timp mai exista lanturi care pot fi parcurse de la start la final, continuam sa le parcurgem adaugand flux:
    while (bfs()) {
        //caut bottleneck-ul, reprezentand noul flux:
        int min = INT_MAX;
        int aux = n;
        while (aux = anc[aux]) {
            if (rez[anc[aux]][aux] < min)
                min = rez[anc[aux]][aux];
            aux = anc[aux];
        }

        //updatez matricea reziduala, adaugand noul flux:
        aux = n;
        while (aux != 0) {
            rez[anc[aux]][aux] -= min;
            rez[aux][anc[aux]] += min;
            aux = anc[aux];
        }

        maxFlow += min;
    }

    ofstream fout("maxflow.out");
    fout << maxFlow;
    std::cout << maxFlow;
    fout.close();
}


//citirea datelor: arcele se memoreaza intr o lista de adiacenta neorientata, pentru ca in graful rezidual avem si drumuri inainte si drumuri inapoi, iar graful rezidual
//e memorat intr o matrice de adiacenta separata, unde adiacenta a doua noduri este caracterizata de fluxul care mai poate trece de la nodul 1 la nodul 2, respectiv fluxul
//care trece deja de la nodul 2 la nodul 1
void citire() {
    ifstream fin("maxflow.in");
    int nod1, nod2, cap;
    fin >> n >> m;
    adj.resize(n + 1);
    rez.resize(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        fin >> nod1 >> nod2 >> cap;
        adj[nod1].push_back(nod2);
        adj[nod2].push_back(nod1);
        rez[nod1][nod2] = cap;
    }
}

int main()
{
    citire();
    edmondsKarp();
    return 0;
}