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

using namespace std;

ofstream fout("maxflow.out");

//1. a) algoritmul edmonds-karp

int n, m, maxFlow;
vector<vector<int>> adj, rez, oriented;
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();

        if (curr == n)
            continue;

        for (long long 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;
            }
        }
    }
    return viz[n];
}

//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()) {
        //pentru toate drumurile care au dus la final:
        for (long long i = 0; i < adj[n].size(); i++)
        {
            if (!viz[adj[n][i]])
                continue;
            //caut bottleneck-ul, reprezentand noul flux:
            int aux = adj[n][i];
            int min = rez[aux][n];
            while (anc[aux] != 0) {
                if (rez[anc[aux]][aux] < min)
                    min = rez[anc[aux]][aux];
                aux = anc[aux];
            }

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

            maxFlow += min;
        }
    }

    fout /* << "Flux maxim: "*/ << maxFlow << "\n";
}


//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));
    oriented.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);
        oriented[nod1][nod2] = 1;
        rez[nod1][nod2] = cap;
    }
}


//b) taietura minima: ma folosesc de starea vectorului de noduri vizitate dupa ultima parcurgere bfs, cea nereusita, iar taietura minima e formata din
//arcele care duc de la noduri vizitate la noduri nevizitate:
void taieturaMinima() {
    fout << "Taietura minima: \n";
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (viz[i] && !viz[j] && oriented[i][j] == 1)
                fout << i << " - " << j << endl;
    fout.close();
}

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