#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adjList;

int N, M;

vector<vector<int>> C;
vector<vector<int>> F;

vector<int> parent;

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

int S, D;

void citireGrafTastatura()
{
    // Se citeste numarul de noduri si nr de muchii, dupa care se citesc muchiile

    cin >> N >> M;

    int x, y, c;

    S = 1;
    D = N;

    adjList = vector<vector<int>>(N + 1, vector<int>());

    // Se citesc muchiile, fiecare avand un cost asociat
    for (int i = 1; i <= M; i++)
    {
        cin >> x >> y >> c;
        adjList[x].push_back(y);

        // Se introduce si muchia inversa de capacitate 0
        adjList[y].push_back(x);

        C[x][y] += c;
        C[y][x] = 0;
        F[x][y] = 0;
        F[y][x] = 0;
    }
}

void citireGrafFisier()
{
    // Se citeste numarul de noduri si nr de muchii, dupa care se citesc muchiile

    fin >> N >> M;

    S = 1;
    D = N;

    C = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
    F = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));

    int x, y, c;

    adjList = vector<vector<int>>(N + 1, vector<int>());

    // Se citesc muchiile, fiecare avand un cost asociat
    for (int i = 1; i <= M; i++)
    {
        fin >> x >> y >> c;
        adjList[x].push_back(y);
        adjList[y].push_back(x);
        C[x][y] += c;
    }
}

void fordFulkerson(int sursa, int destinatie)
{

    int fluxmax = 0;

    // Facem BFS-uri pana cand nu mai gasim niciun drum de crestere (aka lant nesaturat / augumenting path)

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

    do
    {

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

        // Se adauga in coada nodul sursa

        q.push(sursa);

        visited[sursa] = true;

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

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

            // Trecem prin vecinii nevizitati care inca mai pot primi flux

            for (int i = 0; i < adjList[nodCurent].size(); i++)
            {

                int vecin = adjList[nodCurent][i];

                if (!visited[vecin] && C[nodCurent][vecin] - F[nodCurent][vecin] > 0)
                {

                    // Actualizam capacitatea minima nenula de pe lant

                    visited[vecin] = true;

                    q.push(vecin);

                    parent[vecin] = nodCurent;

                    if (vecin == destinatie)
                    {
                        destinationReached = true;
                        break;
                    }
                }
            }
        }

        if (destinationReached)
        {

            // // Trecem prin fiecare muchie care apartine lantului si actualizam fluxul (respectiv capacitatea reziduala)

            // int curent = destinatie;

            // while (parent[curent] != -1)
            // {

            //     if (parent[curent] != -1 && curent != parent[curent])
            //     {
            //         if (bottleneck == -1 || C[parent[curent]][curent] - F[parent[curent]][curent] < bottleneck)
            //         {
            //             bottleneck = C[parent[curent]][curent] - F[parent[curent]][curent];
            //         }
            //     }

            //     curent = parent[curent];
            // }

            // // cout << "S-a gasit un drum de crestere de la sursa la destinatie cu capacitate egala cu " << bottleneck << " si cu urmatoarele path-uri:\n";

            // curent = destinatie;

            // while (parent[curent] != -1)
            // {

            //     // printf("(%d %d) ", parent[curent], curent);

            //     // Adaugam flux pe muchia directa si scadem flux de pe muchia inversa
            //     F[parent[curent]][curent] += bottleneck;
            //     F[curent][parent[curent]] -= bottleneck;

            //     curent = parent[curent];
            // }

            // fluxmax += bottleneck;

            // 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

            int cNode = N;
            int pNode = N;

            // Variabila ce retine fluxul maxim pe care putem sa il aducem pe un path de ameliorare. Pentru un anumit lant, acesta va fi egal cu minimul dintre capacitatile reziduale
            // ale muchiilor ce compun lantul respectiv

            bottleneck = -1;

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

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

                cNode = pNode;

                pNode = parent[pNode];
            }

            cNode = N;
            pNode = N;

            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];
            }

            fluxmax += bottleneck;

            augumentingPathFound = true;
        }
        else
        {
            augumentingPathFound = false;
        }

        // cout << "\n";

    } while (augumentingPathFound);

    // cout << "Fluxul maxim este egal cu " << fluxmax << "\n";
    cout << fluxmax;
}

int main()
{

    citireGrafFisier();

    fordFulkerson(1, N);

    return 0;
}