#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

#define INFINIT INT_MAX

using namespace std;

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

class Graf {
private:
    int nrNoduri;
    vector<vector<int>> capacitate; // Matricea capacităților
    vector<vector<int>> flux;       // Matricea fluxului

public:
    explicit Graf(int nrNoduri);

    int rezolvaMaxFlow(int sursa, int destinatie, int &nrMuchii);

private:
    int maxFlowBFS(int sursa, int destinatie, vector<int> &tati);
};

Graf::Graf(const int nrNoduri) {
    this->nrNoduri = nrNoduri;
    capacitate = vector<vector<int>>(nrNoduri + 1, vector<int>(nrNoduri + 1, 0));
    flux = vector<vector<int>>(nrNoduri + 1, vector<int>(nrNoduri + 1, 0));
}

// BFS pentru a găsi un drum augmentant și a determina fluxul maxim posibil pe acest drum
int Graf::maxFlowBFS(int sursa, int destinatie, vector<int> &tati) {
    fill(tati.begin(), tati.end(), -1);
    queue<pair<int, int>> coada;
    coada.push({sursa, INFINIT});
    tati[sursa] = -2; // Marchez sursa ca vizitată cu o valoare specială

    while (!coada.empty()) {
        int nod = coada.front().first;
        int fluxMinim = coada.front().second;
        coada.pop();

        for (int vecin = 1; vecin <= nrNoduri; vecin++) {
            if (tati[vecin] == -1 && capacitate[nod][vecin] > flux[nod][vecin]) { 
                tati[vecin] = nod;
                int fluxNou = min(fluxMinim, capacitate[nod][vecin] - flux[nod][vecin]);
                if (vecin == destinatie) return fluxNou;
                coada.push({vecin, fluxNou});
            }
        }
    }
    return 0;
}

int Graf::rezolvaMaxFlow(int sursa, int destinatie, int &nrMuchii) {
    // Citire muchii și inițializare capacități
    for (int i = 1; i <= nrMuchii; i++) {
        int u, v, cap;
        fin >> u >> v >> cap;
        capacitate[u][v] += cap; // Dacă există mai multe muchii între aceleași noduri, adunăm capacitatea
    }

    vector<int> tati(nrNoduri + 1);
    int fluxMaxim = 0, fluxNou;

    while ((fluxNou = maxFlowBFS(sursa, destinatie, tati))) {
        fluxMaxim += fluxNou;
        for (int nod = destinatie; nod != sursa; nod = tati[nod]) {
            int parinte = tati[nod];
            flux[parinte][nod] += fluxNou;
            flux[nod][parinte] -= fluxNou; // Flux invers pentru muchii reziduale
        }
    }
    return fluxMaxim;
}

int main() {
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri);
    fout << g1.rezolvaMaxFlow(1, nrNoduri, nrMuchii);

    fin.close();
    fout.close();
    return 0;
}