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

using namespace std;

int N, M, x, y, c;
vector<int> adjList[1024];

// Matrice ce retine capacitatea maxima pentru fiecare muchie in parte

int C[1024][1024];

// Matrice ce retine fluxul curent pentru fiecare muchie in parte

int F[1024][1024];

int main() {

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

    fin >> N >> M; 

    for(int i = 0; i < M; ++i) {
        fin >> x >> y >> c;
        adjList[x].push_back(y);
        // Construim direct graful rezidual, adaugam si muchia (y,x) in lista de adiacenta
        adjList[y].push_back(x);

        // Capacitatea pe (x, y) este c. 
        C[x][y] += c;
    }

    // Sursa este 1 
    int S = 1;
    // Destinatia este N 
    int D = N;

    // Daca am gasit sau nu un path de ameliorare, ne ajuta sa stim cand ne oprin din a face BFS pe graful rezidual 

    bool augumentationPathFound = false;

    // Coada ce va fi folosita pentru parcurgerea BF

    queue<int> q;

    // Vector ce va retine daca un nod este vizitat sau nu in cadrul parcurgerii

    vector<bool> visited;

    // Vectorul de tati al arborelui generat de BFS 

    vector<int> parent; 

    // Daca am ajuns la nodul destinatie in BFS 

    bool destinationReched; 

    // Variabila ce va retine la final flow-ul maxim si va reprezenta suma flow-urilor de pe toate drumurile de ameliorare gasite

    int totalFlow = 0;

    do {

        // Pentru fiecare iteratie a BFS-ului trebuie sa resetam coada, vectorul visited, vectorul de tati si destinationReached

        q = queue<int>();
        visited = vector<bool>(N+1, false);
        parent = vector<int>(N+1, -1);
        destinationReched = false;

        // Incepem prin a introduce in coada nodul de start

        q.push(S);
        visited[S] = true;

        // Cat timp coada nu este vida

        while(!q.empty() && !destinationReched) {

            // Scoatem cel mai vechi nod din coada si il marcam ca si vizitat

            auto currentNode = q.front();
            q.pop();

            if(currentNode == D) {
                continue;
            }

            // Trecem prin fiecare dintre nodurile vecine cu nodul curent

            for(int j = 0; j < adjList[currentNode].size(); j++) {
                auto currentNeighbor = adjList[currentNode][j];

                // Daca vecinul nu a fost inca vizitat si catre el capacitatea reziduala este mai mare decat 0 (capacitate - flux), atunci adaugam nodul in coada 
                
                if(!visited[currentNeighbor] && C[currentNode][currentNeighbor] - F[currentNode][currentNeighbor] > 0) {


                    visited[currentNeighbor] = true;

                    q.push(currentNeighbor);

                    // Marcam si nodul vecin ca fiind vizitat 
                    visited[currentNeighbor] = true;

                    // Actualizam parintele nodului vecin (care este nodul curent)

                    parent[currentNeighbor] = currentNode;

                    // Daca am ajuns cumva la nodul destinatie, atunci oprim BFS-ul

                    // if(currentNeighbor == D) {
                    //     destinationReched = true;
                    //     break;
                    // }
                }
            }

            if(visited[D]) {
                destinationReched = true;
                break;
            }
        }

        if(destinationReched) {
            // cout << "S-a gasit un path de ameliorare vectorul de tati este: ";
            // for(auto x: parent) {
            //     cout << x << " ";
            // }


            //cout << " , iar muchiile ce compun path-ul sunt: ";
            // Daca am gasit un drum de ameliorare, atunci trebuie sa il reconstruim din vectorul de tati si sa actualizam fluxul muchiilor ce fac parte din acel drum



        for(int kk = 0; kk < adjList[D].size(); ++kk) {

            int currentNeighbor = adjList[D][kk];
            if(F[currentNeighbor][D] == C[currentNeighbor][D] || !visited[currentNeighbor]) {
                continue;
            }

            parent[D] = currentNeighbor;

            int cNode = D;
            int pNode = D;
            int bottleneck = -1; 

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

                if(pNode != -1 && pNode != cNode) {
                    //cout << "(" << pNode << " " << cNode << ") ";
                    if(bottleneck == -1 || C[pNode][cNode] - F[pNode][cNode] < bottleneck) {
                        bottleneck = C[pNode][cNode] - F[pNode][cNode];
                    }
                }

                cNode = pNode;

                pNode = parent[pNode];
            }

            //cout << "Pt path-ul de mai sus fluxul maxim pe care il putem adauga este egal cu " << bottleneck << "\n";

            cNode = D;
            pNode = D;

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

                if(pNode != -1 && pNode != cNode) {
                    // Scadem bottleneck-ul din muchia din graful initial si adaugam la muchia inversa bottleneck-ul cu semn schimbat
                    F[pNode][cNode] += bottleneck;
                    F[cNode][pNode] -= bottleneck;       
                }

                cNode = pNode;

                pNode = parent[pNode];
            }

            totalFlow += bottleneck;

            //cout << "\n";
            augumentationPathFound = true;

        }
        } else {
            augumentationPathFound = false;
        }

    } while(augumentationPathFound);


    fout << totalFlow;  

    return 0;
}