#include <vector>
#include <queue>
#include <fstream>
#include <climits>
#include <iostream>
using namespace std;
ifstream fileIn("maxflow.in");
ofstream fileOut("maxflow.out");


class Graph {
    int N;
    int M;
    vector<int> prev_in_bfs;
    vector<vector<int>> list_adj;
    vector<bool> visited;
    vector<vector<int>> capacities;


    public:
        void read();
        int bfs(int s, int t);
        int maxflow(int source, int target);
        int getNoNodes(){
            return N;
            }

};

void Graph:: read() {
    fileIn >> N >> M;
    // resize
    list_adj.resize(N + 1);
    visited.resize(N + 1);
    prev_in_bfs.resize(N + 1);
    capacities.resize(N+1);

    for(int i = 1; i < (int) capacities.size(); i++) {
        capacities[i].resize(N + 1, 0);
    }

    int a, b, c;
    for(int i=1; i<= M; i++) {
            fileIn >> a >> b >> c;
            list_adj[a].push_back(b);
            capacities[a][b] = c;
    }

}

int Graph::bfs(int s, int t) {
    //filling prev and visited vectors with default values
    fill(prev_in_bfs.begin(), prev_in_bfs.end(), -1);
    fill(visited.begin(), visited.end(), false);
    // queue for bfs
    queue<pair<int,int>> q_bfs;
    //visiting the start node and adding to the queue
    q_bfs.push({s, INT_MAX});
    visited[s] = true;
    int bottleneck;
    while(!q_bfs.empty()) {
        auto curr = q_bfs.front();
        int curr_node = curr.first;
        int curr_flow = curr.second;
        q_bfs.pop();

        for( auto node: list_adj[curr_node]) {
            // for every adj node
            int flow = capacities[curr_node][node];
            if(!visited[node] && flow) { // if the node it s not visited in this bfs and the edge have capacity
                //we visit it and set its prev node
                visited[node] = true;
                prev_in_bfs[node] = curr_node;
                //we calculate bottleneck as minimum on the current path from source to target
                bottleneck = min(curr_flow, flow);
                if (node ==  t) {
                    return bottleneck;
                }
                q_bfs.push({node, bottleneck});
            }
    }

}
        return 0;

}

int Graph::maxflow(int source, int target) {
    int flow = 0;

    int bottleneck;
    bottleneck = bfs(source,target);
    while(bottleneck !=0) {
        flow += bottleneck;
        int curr_node = target; // traverse the path in reverse order to update capacity
        for(curr_node; curr_node != source; curr_node = prev_in_bfs[curr_node]) {
            capacities[prev_in_bfs[curr_node]][curr_node] -= bottleneck; //decreasing forward edge capacity
            capacities[curr_node][prev_in_bfs[curr_node]] += bottleneck; // increasing the reversed edge capacity
        }

        bottleneck = bfs(source, target);
    }
    return flow;
}

int main()  {
    Graph my_graph;
    my_graph.read();
    fileOut << my_graph.maxflow(1, my_graph.getNoNodes());



    return 0;

}