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


class FlowNetwork {
    int n, m, s, t;
    struct edge {
        int src, dst, capacity, flow;
        edge* back;
    };
    vector<vector<edge*>> adj;
    vector<edge*> parent;
    void appendEdge(int x, int y, int capacity) {
        edge* e1 = new edge;
        edge* e2 = new edge;

        e1->back = e2;
        e2->back = e1;
    
        e1->src = x;
        e1->dst = y;
        e1->capacity = capacity;
        e2->flow = e1->flow = 0;
        e2->src = y;
        e2->dst = x;
        e2->capacity = 0;

        adj[x].push_back(e1);
        adj[y].push_back(e2);
    }

public:
    FlowNetwork(int _n, int _m, int source, int term, vector<tuple<int, int, int>>& edges);
    void changeSource(int _s) { s = _s; }
    void changeTerminal(int _t) { t = _t; }
    bool bfs(int src, int term);
    int findMaxFlow();
};

// If you want bipartite matching, you must give the capacity of 1 to all edges
// an edge from edges vector has the following form : (src, dst, capacity)
FlowNetwork::FlowNetwork(int _n, int _m, int source, int term, vector<tuple<int, int, int>>& edges): n(_n), m(_m), s(source), t(term) {
    adj.resize(n + 1);
    parent.resize(n + 1);

    int x, y, c;
    for(auto edge : edges) {
        x = get<0>(edge);
        y = get<1>(edge);
        c = get<2>(edge);
        appendEdge(x, y, c);
    }
}

bool FlowNetwork::bfs(int src, int term) {
    fill(parent.begin(), parent.end(), nullptr);
    queue<int> q;
    q.push(src);

    int currNode;
    while(!q.empty()) {
        currNode = q.front();
        q.pop();        

        for(auto nextEdge : adj[currNode])  {
            int nextNode = nextEdge->dst;
            if(!parent[nextNode] && nextEdge->capacity - nextEdge->flow > 0) {
                parent[nextNode] = nextEdge;
                if(nextNode != term) {
                    q.push(nextNode);
                }
            }
        }
    }   

    return parent[term] != nullptr;
}

int FlowNetwork::findMaxFlow() {
    int maxFlow = 0;
    while(bfs(s, t)) {
        for(auto terminalEdge : adj[t]) {
            if(terminalEdge->back->capacity - terminalEdge->back->flow <= 0 || !parent[terminalEdge->dst])        
                continue;
            
            parent[t] = terminalEdge->back;
            int minValOnPath = 1e6;
            for(auto current = t; current != s; current = parent[current]->src)
                minValOnPath = min(minValOnPath, parent[current]->capacity - parent[current]->flow);
            
            if(!minValOnPath)    
                continue;
            
            maxFlow += minValOnPath;
            
            for(auto current = t; current != s; current = parent[current]->src) {
                parent[current]->flow += minValOnPath;
                parent[current]->back->flow -= minValOnPath;
            }
        }
    }

    return maxFlow;
}

int main() {
    ifstream in("maxflow.in");
    ofstream out("maxflow.out");
    int n, m, x, y, c;
    vector<tuple<int, int, int>> edges;
    
    in >> n >> m;
    for(int i = 0; i < m; ++ i) {
        in >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    FlowNetwork graph{n, m, 1, n, edges};
    out << graph.findMaxFlow();

    return 0;
}