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

using namespace std;

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

struct edge {
    int f, c;
} M[N][N];

int n;
vector<int> g[N];
vector<int> h[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);
        h[y].push_back(x);
        M[x][y] = {0, c};
    }
    source = 1;
    terminal = n;
}

int Daddy[N];
bool viz[N];
queue<int> q;

bool BFS() {
    for(int i = 1; i <= n; i++)
        Daddy[i] = 0, 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].c == M[nod][son].f) continue;

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

        for (auto son : h[nod]) {
            if(viz[son]) continue;
            if(M[son][nod].f == 0) continue;

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

    return false;
}

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

    int prev = Daddy[nod];
    
    if(prev > 0) {
        auto &m = M[prev][nod];
        mn = min(mn, m.c - m.f);
        Review(prev, mn);
        m.f += mn;
    } else {
        prev = -prev;
        auto &m = M[nod][prev];
        mn = min(mn, m.f);
        Review(prev, mn);
        m.f -= mn;
    }
}

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

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

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