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

constexpr int maxn = 1010;

vector<int> vec[maxn];
int n, flux[maxn][maxn], cap[maxn][maxn], excess[maxn], label[maxn], curr_edge[maxn];
bool in_queue[maxn] = {};
vector<int> de_viz;

void push(int x, int y){
    const int delta = min(excess[x], cap[x][y] - flux[x][y]);

    excess[x] -= delta;
    excess[y] += delta;
    flux[x][y] += delta;
    flux[y][x] -= delta;

    if(!in_queue[y] && excess[y] && y != 1 && y != n){
        in_queue[y] = true;
        de_viz.push_back(y); }
    }

void relabel(int x){
    label[x] = 1e9;
    for(auto y : vec[x])
        if(cap[x][y] > flux[x][y])
            label[x] = min(label[x], label[y] + 1); }

void discharge(){
    const int x = de_viz.back(), curr_label = label[x];
    de_viz.pop_back();
    in_queue[x] = false;
    
    while(excess[x] > 0 && curr_label == label[x]){
        for(auto y : vec[x])
            if(cap[x][y] > flux[x][y] && label[x] == label[y] + 1)
                push(x, y);
        relabel(x); }

    if(excess[x] > 0){
        in_queue[x] = true;
        de_viz.push_back(x); } }

void init_labels(){
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int x = q.back();
        q.pop();
        for(auto y : vec[x]){
            if(y != 1 && y != n && cap[x][y] == 0 && label[y] == 0){
                label[y] = label[x] + 1;
                q.push(y); } } } }

int max_flow(){
    label[1] = n;
    init_labels();
    for(auto y : vec[1]){
        excess[1] = 1e9;
        push(1, y); }

    sort(begin(de_viz), end(de_viz), [](int x, int y){
        return label[x] < label[y]; });

    while(!de_viz.empty())
        discharge();

    return excess[n]; }

int main(){
    ifstream f("maxflow.in");
    ofstream g("maxflow.out");
    int m;

    f >> n >> m;

    for(int i = 0, x, y, z; i < m; ++i){
        f >> x >> y >> z;
        vec[x].push_back(y);
        vec[y].push_back(x);
        cap[x][y] = z; }

    for(int i = 1; i <= n; ++i)
        random_shuffle(begin(vec[i]), end(vec[i]));

    g << max_flow() << endl; }