#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
// #include <bits/std++.h>
#define in  fin
#define out fout

using namespace std;
const int NMAX = 1001;

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

struct muchie{
    int x, y;
    int pereche;
    int f, c; // f si c de la.. de la... (flow si capacitate) uh... flowey si.. si.. uhhh... nush cine e cu c sunt un larper
    // am mai mentionat ca ma enerveaza f tare flowery?
    // ieri mi-o mancat zilele
    // m-am suparat asa tare ca m-am pus sa colorez o mandala dinaia cu pisici
    // am stat 3h sa colorez de nervi pe acel stupid boss fight
    // tho!! am vazut ceva gameplay la reanimal (jocu ala de dupa little nightmares)
    // and it is PEAK
    // m-as mai uita o data cand is actually consious ca il aveam ca background noise si nu am inteles mare lucru
    // but the visuals are PEAK
    // multumesc superhorrorbro mike here ca ai facut jocul pe canal i love you my fav youtuber
};

vector<muchie> mch; // inteleg ca trb sa tin muchiile dupa index, nu ca un graf

// get out e o melodie acc destul de buna chiar pt tot larpu de pe insta
// the real ones jucau secret neighbour cand se juca maxinfinit si pisica miau miau
// *emojiul ala cu mana cu 2 dejete in sus in gen peace (✌️)*
// si can't be erased e peak
// da gen ala e bendy song deci normal ca e peak

// o sa fiu sincer i did take a lil peek la sursa emei sa vad o sursa clean si frumoasa inainte sa scriu eu ceva bazaconii
// but now i'm ready sa implementez acest flux de gen 15 ori

int susie, noelle; // initial era sursa si dupa aia lowk suna ca si susie
// si daca e susie ofc ca perechea trb sa fie noelle
// has the deltarune brainrot gone too far?

// ok deci prima data facem un BFS sa vedem la ce noduri pot ajunge cu muchii nesaturate

bool mrc[NMAX];
pair<int, int> last[NMAX]; // de la cine am venit si ce muchie am folosit
// poate fi doar muchie dar SYBAU e mai frumos asa

vector<int> g[NMAX];
// g[i] tine indicii muchiilor care pleaca din i

int n, m;

void fa_bfs_te_rog(){
    for(int i = 1; i <= n; i++){ // indexare malefica malevolenta de la 1
        last[i].first = 0; last[i].second = -1;
        mrc[i] = 0;
    }

    queue<int> q;
    q.push(susie); // da, stiu ca in problema asta susie e 1 si noelle e n, but let me enjoy my deltarune brainrot
    mrc[susie] = 1;

    while(!q.empty()){
        int x = q.front(); q.pop();
        for(const int &cine_a_intrebat : g[x]){
            int y = mch[ cine_a_intrebat ].y;
            if( !mrc[y] && mch[ cine_a_intrebat ].f < mch[ cine_a_intrebat ].c ){
                q.push(y);
                mrc[y] = 1;
                last[y].first = x;
                last[y].second = cine_a_intrebat;
            }
        }
    }
}

// apoi am nevoie de o functie ca sa gasesc minimul pe un drum

int gaseste_minimul_te_rog(int nod, int minim_ude){
    while(last[nod].second != -1){
        minim_ude = min(minim_ude, mch[ last[nod].second ].c - mch[ last[nod].second ].f);
        // cerr << "----> fac pathul nod = " << nod << " minim = " << minim_ude << " parinte = " << last[nod].first << '\n';
        nod = last[nod].first;
    }
    return minim_ude; // bile ude
    // scuze
}

void satureaza_pathul_te_rog(int nod, int val){
    while(last[nod].second != -1){
        mch[ last[nod].second ].f += val;
        mch[ mch[ last[nod].second ].pereche ].f -= val;

        nod = last[nod].first;
    }
}
// should be good

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    in >> n >> m;
    vector< pair<int, int> > ralsei;
    for(int i = 0; i < m; i++){
        int x, y, c; in >> x >> y >> c;
        int id = mch.size(), idp = mch.size() + 1;
        mch.push_back({x, y, idp, 0, c});
        mch.push_back({y, x, id,  0, 0});

        if(y == n) ralsei.push_back({id, x});
        if(x == n) ralsei.push_back({idp, y});

        g[x].push_back(id);
        g[y].push_back(idp);
    }

    susie = 1; noelle = n;
    // i am susie deltarune
    // i like sealing fountains too
    // and my 2 best friends are kris
    // aaaaaaand raaaaalseeeeei
    // we are here to save the day
    // i like girls and that's okay
    // i am susie
    // from deeelllltaruuuuneee

    int total = 0;
    while(true){
        fa_bfs_te_rog(); // multumesc
        if(!mrc[noelle]) break; // nu pot aj la final cu dinalea nesaturate deci nu pot sa fac mai bine
        // cerr << "am intrat! lesgo\n";
        for(const pair<int, int> &cine : ralsei){ // cine e in ralsei (ce) (eu) (ce) (de ce am formulat-o asa)
            int cop = cine.second;
            int id = cine.first;

            if(!mrc[cop]) continue; // ge ge getoutt
            if(mch[id].f == mch[id].c) continue; // dinou ge ge getoutt

            // cerr << "--> il pot continua pe " << cop << '\n';
            // cerr << "--> incerc sa ii fac pathul.. pana acuma am minimul = " << mch[id].c - mch[id].f << '\n';

            int perchance = gaseste_minimul_te_rog(cop, mch[id].c - mch[id].f); // multumesc!
            if(perchance == 0) continue;

            // cerr << "--> cu minimul = " << perchance << '\n';

            satureaza_pathul_te_rog(cop, perchance);
            total += perchance;

            mch[ id ].f += perchance;
            mch[ mch[ id ].pereche ].f -= perchance;
        }
    }

    // cout << "cum arata muchiile la final : \n";
    // for(const muchie &x : mch){
    //     cout << "( " << x.x << " , " << x.y << " ) --> f = " << x.f << " c = " << x.c << " perece = " << x.pereche << '\n'; 
    // }

    out << total << '\n';

    return 0;
}