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

using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int destinatie, capacitate[1001][1001], parinte[1001];
vector<vector<int> > muchii;

void citeste();
int edmondsKarp();

int main()
{
    citeste();
    g << edmondsKarp();
    g.close();
    return 0;
}

bool bfs() {
    vector<bool> ap;
    queue<int> q;
    ap.resize(destinatie + 1);
    // Adaug sursa in coada
    q.push(1);
    ap[1] = true;
    // Cat timp mai am elemente in coada
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        // Verific daca pot sa mai pun flow pe muchiile catre vecinii nodului curent
        for(auto it : muchii[nod]){
            // Daca vecinul nu e vizitat si se poate adauga flow pe muchia de la nod la el
            if(!ap[it] && capacitate[nod][it]){
                // Parintele vecinului este nodul curent si vecinul e vizitat si adaugat in coada
                parinte[it] = nod;
                ap[nod] = true;
                q.push(it);
                // Daca vecinul este destinatia atunci am gasit un drum bun
                if(it == destinatie)
                    return true;
            }
        }
    }
    // Daca ajung aici nu mai sunt drumuri bune
    return false;
}

int edmondsKarp()
{
    int raspuns = 0;
    // Cat timp mai gasesc un drum pana la destinatie pe care pot adauga flow
    while(bfs()) {
        // Caut drumuri mai bune in toti vecinii destinatiei
        for(auto it : muchii[destinatie]) {
            parinte[destinatie] = it;
            // Determin flow-ul maxim pe care il pot adauga drumului
            int nod = destinatie, newFlow = 1000000000;
            while(nod != 1) {
                int par = parinte[nod];
                if(capacitate[par][nod] < newFlow) {
                    newFlow = capacitate[par][nod];
                }
                nod = par;
            }
            // Adaug la toate muchiile de pe drum flow-ul maxim
            nod = destinatie;
            while(nod != 1) {
                int par = parinte[nod];
                capacitate[par][nod] -= newFlow;
                capacitate[nod][par] += newFlow;
                nod = par;
            }
            // Adaug flow-ul gasit la raspuns
            raspuns += newFlow;
        }
    }
    return raspuns;
}

void citeste()
{
    int m;
    f >> destinatie >> m;
    muchii.assign(destinatie + 1, vector<int>());
    while(m--) {
        int x, y, c;
        f >> x >> y >> c;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
        capacitate[x][y] = c;
    }
    f.close();
}