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

using namespace std;

int n, m, a, b, c;
vector<int> lista_adiacenta[1024];
int cost[1024][1024];
int flux[1024][1024];

//Ford-Fulkerson

int main() {

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

    fin >> n >> m;

    //cream lista de adiacenta si costul muchiilor , precum si lista de drum inapoi
    for (int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        lista_adiacenta[a].push_back(b);
        lista_adiacenta[b].push_back(a);
        cost[a][b] += c;
    }

    int sursa = 1;
    int destinatie = n;
    bool gasireLant = false;
    queue<int> coada;
    vector<bool> viz;
    vector<int> tata;
    bool gasireDestinatie;
    int total = 0;

    do {
        coada = queue<int>();
        viz = vector<bool>(n + 1, false);
        tata = vector<int>(n + 1, -1);
        gasireDestinatie = false;
        coada.push(sursa);
        viz[sursa] = true;

        //cat timp coada nu e goala si nu am ajuns la destinatie
        while (!coada.empty() && !gasireDestinatie) {
            //luam elementul curent si il scoatem din coada
            int nodCurent = coada.front();
            coada.pop();
            if (nodCurent == destinatie) 
            {
                continue;
            }

            //parcurgem lista de vecini a nodului curent
            for (int j = 0; j < lista_adiacenta[nodCurent].size(); j++) {
                int vecin = lista_adiacenta[nodCurent][j];
                //daca n am vizitat vecinul si costul-flux > 0
                if (!viz[vecin] && cost[nodCurent][vecin] - flux[nodCurent][vecin] > 0) {
                    viz[vecin] = true;
                    coada.push(vecin);
                    viz[vecin] = true;
                    tata[vecin] = nodCurent;
                }
            }

            //daca am vizitat destinatia
            if (viz[destinatie]) {
                gasireDestinatie = true;
                break;
            }
        }

        //daca am gasit destinatia
        if (gasireDestinatie) {
            int vecin = 0;

            //parcurgem lista de adiacenta pornind de la destinatie
            for (int t = 0; t < lista_adiacenta[destinatie].size(); ++t) {

                //luam vecinii si parcurgem drumul invers pana la sursa, actualizand pe parcurs fluxul 
                vecin = lista_adiacenta[destinatie][t];

                if (flux[vecin][destinatie] == cost[vecin][destinatie] || !viz[vecin])
                {
                    continue;
                }

                tata[destinatie] = vecin;

                int cNode = destinatie;
                int pNode = destinatie;
                int fluxC = -1;

                while (true) {
                    if (pNode == -1) {
                        break;
                    }

                    if (pNode != -1 && pNode != cNode) {
                        if (fluxC == -1 || cost[pNode][cNode] - flux[pNode][cNode] < fluxC) {
                            fluxC = cost[pNode][cNode] - flux[pNode][cNode];
                        }
                    }
                    cNode = pNode;
                    pNode = tata[pNode];
                }

                cNode = destinatie;
                pNode = destinatie;

                while (true) {
                    if (pNode == -1) {
                        break;
                    }

                    if (pNode != -1 && pNode != cNode) {
                        flux[pNode][cNode] += fluxC;
                        flux[cNode][pNode] -= fluxC;
                    }
                    cNode = pNode;
                    pNode = tata[pNode];
                }
                total += fluxC;
                gasireLant = true;
            }
        }
        else
        {
            gasireLant = false;
        }

    } while (gasireLant);
    fout << total;

    return 0;
}