#include <bits/stdc++.h>
using namespace std;
#define MAXN 1005

ifstream fin("");
ofstream fout("");

class Graf {
private:
    vector<int> neighbours[MAXN];
    int capacity[MAXN][MAXN], nodes, edges, flow;
public:
    void maximalFlow(); 
    void read(string file);
    void print(string file);
};

void Graf::read(string file) {
    ifstream fin(file);
    fin >> nodes >> edges;
    int x, y;
    for (int i = 0; i < edges; ++i) {
        fin >> x >> y;
        neighbours[x].push_back(y);
        neighbours[y].push_back(x);
        fin >> capacity[x][y];
    }     
    fin.close();
}

void Graf::maximalFlow() {
    int father[nodes + 1], verify[nodes + 1]; 
    queue<int> q;
    while (true) {
        for (int i = 1; i <= nodes; ++i) {
            verify[i] = 0;
        }
        q.push(1);
        verify[1] = 1;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (auto next : neighbours[node]) {
                if (!verify[next] && capacity[node][next] > 0) {
                    q.push(next);
                    verify[next] = 1;
                    father[next] = node;
                }
            }
        }
        if (!verify[nodes]) {
            break;
        }
        for (auto next : neighbours[nodes]) {
            if(capacity[next][nodes] <= 0 || !verify[next]) {
                continue;
            }
            father[nodes] = next;
            int maxFlow = 110000; 
            for (int dest = nodes; dest != 1; dest = father[dest]) {
                maxFlow = min(maxFlow, capacity[father[dest]][dest]);
            }
            for (int dest = nodes; dest != 1; dest = father[dest]) {
                capacity[father[dest]][dest] -= maxFlow;
                capacity[dest][father[dest]] += maxFlow;
            }
            flow += maxFlow;    
        }
    }
}

void Graf::print(string file) {
    ofstream fout(file);
    fout << flow;
    fout.close();
}


int main() {
    Graf graf = Graf(); 
    graf.read("maxflow.in");
    graf.maximalFlow();
    graf.print("maxflow.out");
}