#include <iostream>
#include <fstream>
#include <cstring>
#define DMAX 1001
#define CAPMAX 110001 //capacitatea maxima posibila (ip.)

using namespace std;

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

struct nod{
    int val;
    nod * urm;
}*v[DMAX];

int capacitate[DMAX][DMAX];//matrice ce retine capacitatile
int flux[DMAX][DMAX];//matrice ce retine fluxul pe muchii si asimetricile lor - fluxActual
int tata[DMAX];//folosit pentru a retine daca un nod vine din sursa (are tata)

int n, m;//date de intrare
int fluxMaxim;
bool intra[DMAX];//array -uri pt a stabili care e punctul de start si care e destinatia
bool iese[DMAX];

int S, D; //nodul sursa si nodul destinatie

void initializare(){
    for(int i = 1; i <= n; i++){
        v[i] =  NULL;
    }
}

void citire(){
    in >> n >> m;
    initializare();
    for(int i = 1; i <= m; i++){
        int x, y, c;
        in >> x >> y >> c;
        capacitate[x][y] = c;
        iese[x] = true;
        intra[y] = true;

        nod * deAdaugat1 = new nod;
        deAdaugat1 -> val = y;
        deAdaugat1 -> urm = v[x];
        v[x] = deAdaugat1;

        nod * deAdaugat2 = new nod;
        deAdaugat2 -> val = x;
        deAdaugat2 -> urm = v[y];
        v[y] = deAdaugat2;
    }
}

void sursaSiDestinatie(){
    for(int i = 1; i <= n && (S == 0 || D == 0); i++){
        if(iese[i] == false){
            D = i;
        }
        if(intra[i] == false){
            S = i;
        }
    }
}

int bfs(){
    int ok = 0;
    memset(tata, 0, sizeof(tata));
    int coada[DMAX], primul = 1, ultimul = 1;
    coada[1] = S;
    tata[S] = -1;//sursa nu are tata
    while (primul <= ultimul){
        nod * parcurg = v[coada[primul]];
        while(parcurg != NULL){
            if(tata[parcurg -> val] == 0 && capacitate[coada[primul]][parcurg -> val] > flux[coada[primul]][parcurg -> val]){
                if(parcurg -> val != D) {
                    coada[++ultimul] = parcurg->val;
                    tata[parcurg->val] = coada[primul];
                }else{
                    ok = 1;
                }
            }
            parcurg = parcurg -> urm;
        }
        primul++;
    }
    return ok;
}

void dinic(){
    int eDrumLaDestinatie ;
    for(eDrumLaDestinatie = bfs();eDrumLaDestinatie ; eDrumLaDestinatie = bfs()){
        nod * parcurg = v[D];
        while(parcurg != NULL){
            if(tata[parcurg -> val] != 0 && capacitate[parcurg -> val][D] > flux[parcurg -> val][D]) {
                tata[D] = parcurg->val;
                //incep sa o iau inapoi pe drum sa vad care e fluxul minim pe care il pot pune
                int fluxActual = CAPMAX;
                for (int intoarcere = D; intoarcere != S; intoarcere = tata[intoarcere]) {
                    int aux = tata[intoarcere];
                    fluxActual = min(fluxActual,(capacitate[aux][intoarcere] - flux[aux][intoarcere]));
                }

                if (fluxActual > 0) {
                    fluxMaxim += fluxActual;
                    for (int intoarcere = D; intoarcere != S; intoarcere = tata[intoarcere]) {
                        int aux = tata[intoarcere];
                        flux[aux][intoarcere] += fluxActual;
                        flux[intoarcere][aux] -= fluxActual;
                    }
                }
            }
            parcurg = parcurg->urm;
        }
    }
}

int main() {
    citire();//ok
    sursaSiDestinatie();//ok
    dinic();
    out << fluxMaxim;
    return 0;
}