#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

const int INF = 1 << 30;
const int MAX_N = 1005;

int N, M;
vector<int> graph[MAX_N];
int cap[MAX_N][MAX_N];
int flow[MAX_N][MAX_N];
int source, sink;

void read_input();
int maxflow();
bool find_augmenting_path(int father[]);
int rcap(int a, int b);

int main() {
    read_input();
    fout << maxflow();
    return 0;
}

void read_input() {
    fin >> N >> M;
    for (int i = 1, a, b, c; i <= M; i += 1) {
        fin >> a >> b >> c;
        graph[a].push_back(b);
        graph[b].push_back(a);
        cap[a][b] = c;
    }
    source = 1; sink = N;
}

int maxflow() {
    int result = 0;

    int father[MAX_N];
    while (find_augmenting_path(father)) {
        for (auto i: graph[sink]) {
            if (rcap(i, sink) == 0 || father[i] == 0) continue;

            int new_flow = rcap(i, sink);
            for (int node = i; node != source; node = father[node]) {
                new_flow = min(new_flow, rcap(father[node], node));
            }

            if (new_flow == 0) continue;

            flow[i][sink] += new_flow;
            flow[sink][i] -= new_flow;

            for (int node = i; node != source; node = father[node]) {
                flow[node][father[node]] -= new_flow;
                flow[father[node]][node] += new_flow;
            }

            result += new_flow;
        }
    }
    return result;
}

bool find_augmenting_path(int father[]) {
    fill(father, father + N + 1, 0);

    queue<int> q;
    q.push(source);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        if (node == sink) return true;

        for (auto next: graph[node]) {
            if (father[next] == 0 && rcap(node, next) > 0) {
                father[next] = node;
                q.push(next);
            }
        }
    }
    return false;
}

inline int rcap(int a, int b) {
    return cap[a][b] - flow[a][b];
}