#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>

using namespace std;

const int MAX = 1050;

int N, M, Ans;
int dad[MAX];
int F[MAX][MAX], C[MAX][MAX];

vector<int> G[MAX];

void citire() {
    ifstream in("maxflow.in");
    in >> N >> M;
    for(int i = 1, a, b, c; i <= M; i++) {
        in >> a >> b >> c;
        C[a][b] += c;
        G[a].push_back(b);
        G[b].push_back(a);
    } in.close();
}

bool BF() {
    memset(dad, 0, sizeof(dad));
    queue<int> Q;
    dad[1] = 1;
    Q.push(1);

    while(!Q.empty()) {
        int nod = Q.front(); Q.pop();
        if(nod == N) continue;
        for(size_t i = 0; i < G[nod].size(); i++) {
            int dest = G[nod][i];
            if(!dad[dest] && F[nod][dest] != C[nod][dest]) {
                dad[dest] = nod;
                Q.push(dest);
            }
        }
    } return dad[N] != 0;
}

void solve() {
    for(; BF(); ) {
        for(size_t i = 0; i < G[N].size(); i++) {
            int Prev = G[N][i];
            if(!dad[Prev] || F[Prev][N] == C[Prev][N]) 
                continue;
            int FMin = C[Prev][N] - F[Prev][N];
            while(Prev != dad[Prev]) {
                FMin = min(FMin, C[dad[Prev]][Prev] - F[dad[Prev]][Prev]);
                Prev = dad[Prev];
            }
            if(!FMin) continue;
            
            Prev = G[N][i];

            F[Prev][N] += FMin;
            F[N][Prev] -= FMin;

            while(Prev != dad[Prev]) {
                F[dad[Prev]][Prev] += FMin;
                F[Prev][dad[Prev]] -= FMin;
                Prev = dad[Prev];
            }

            Ans += FMin;
        }
    }
}

void afisare() {
    ofstream out("maxflow.out");
    out << Ans << "\n";
    out.close();
}

int main() {
    citire();
    solve();
    afisare();
}