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

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.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];
queue<int> q;

bool BFS() {
    for(int i = 1; i <= n; i++)
        Daddy[i] = -1, viz[i] = false;
    while(!q.empty()) q.pop();
    q.push(source);
    viz[source] = true;
    while(!q.empty()) {
        int nod = q.front();
        q.pop();

        if (nod == terminal) return true;

        for (auto son : g[nod]) {
            if(viz[son]) continue;
            if(M[nod][son].type == +1 && M[nod][son].f == M[nod][son].c) continue;
            if(M[nod][son].type == -1 && M[nod][son].f == 0) continue;

            Daddy[son] = nod;
            viz[son] = true;
            q.push(son);
        }
    }

    return false;
}

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;
    M[nod][Daddy[nod]].f -= m.type * mn;
}

void Rezolvare() {
    while(BFS()) {
        int mn = 2e9;
        Review(terminal, mn);
    }


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

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