#include <iostream>
#include <fstream>
#include <vector>
#define N 1008

using namespace std;

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

int n;
struct muchie {
    int f, c;
    int type;
} M[N][N];
vector<int> g[N];

int source, terminal;

void Citire() {
    int m;
    int x, y, c;
    fin >> n >> m;
    for (int i=1; i<=m; i++) {
        fin >> x >> y >> c;
        g[x].push_back(y); M[x][y] = {0, c, +1};
        g[y].push_back(x); M[y][x] = {0, c, -1};
    }
    source = 1;
    terminal = n;
}

int Daddy[N];
bool viz[N];
bool gasitDrum;

void DFS(int x) {
    viz[x] = true;
    if(x == terminal) gasitDrum = true;
    for(auto nod : g[x]) {
        if(viz[nod]) continue;
        if(M[x][nod].type == +1 && M[x][nod].f == M[x][nod].c) continue;
        if(M[x][nod].type == -1 && M[x][nod].f == 0) continue;

        Daddy[nod] = x;
        DFS(nod);
    }
}

void Review(int nod, int &mn) {
    if(nod == source) return;

    muchie &m = M[Daddy[nod]][nod];
    if(m.type == +1) mn = min(mn, m.c - m.f);
    if(m.type == -1) mn = min(mn, m.f);

    Review(Daddy[nod], mn);

    m.f += m.type * mn;
}

void Rezolvare() {
    gasitDrum = true;
    while(gasitDrum) {
        gasitDrum = false;
        for(int i = 1; i <= n; i++)
            Daddy[i] = -1, viz[i] = false;
        DFS(source);

        int mn = 2e9;
        if (gasitDrum) Review(terminal, mn);
    }


    int flux = 0;
    for(auto nod : g[source])
        flux += M[source][nod].f;
    fout << flux;
}

int main() {
    Citire();
    Rezolvare();
    return 0;
}