#include <fstream>
#include <iostream>
#include <vector>
 
#include <cassert>
#include <ctime>
#include <cstdlib>
using namespace std;
 
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
 
struct Edge {
    int a, b, flow, cap;
    Edge() {
        a = b = flow = cap = 0;
    }
    Edge(int _a, int _b, int _cap) {
        a = _a;
        b = _b;
        cap = _cap;
    }
 
    int other(int _nod) {
        return a + b - _nod;
    }
 
    int getMaxFlow(int _nod) {
        if (_nod == a) {
            return cap - flow;
        } else {
            return flow;
        }
    }
     
    int getReverseMaxFlow(int _nod) {
        return getMaxFlow(other(_nod));
    }
 
    void pumpFlow(int _nod, int _f) {
        if (_nod == a) {
            flow += _f;
        } else {
            flow -= _f;
        }
    }
 
    void pumpReverseFlow(int _nod, int _f) {
        pumpFlow(other(_nod), _f);
    }
};
 
struct Flow {
    static int inf;
    int source, sink, flow, maxNod;
    vector<vector<int> > edgeId;
    vector<Edge> edges;
    
    vector<int> father, que;
 
    Flow() {
        source = sink = flow = maxNod = 0;  
        edgeId.resize(1);
    }
     
    Flow(int _source, int _sink, int _maxNod) {
        source = _source;
        sink = _sink;
        maxNod = _maxNod;
        edgeId.resize(maxNod + 1);
        flow = 0;
        father.resize(maxNod + 1);
        que.resize(maxNod + 1);
    }
 
    void addEdge(int a, int b, int cap) {
        assert(a <= maxNod and b <= maxNod);
        edgeId[a].push_back(edges.size());
        edgeId[b].push_back(edges.size());
        edges.push_back(Edge(a, b, cap));
    }
    
    int pumpFlow() {
        const int notVisited = -1;

        que.clear();
        for (int i = 0; i <= maxNod; ++i) {
        	father[i] = notVisited;
        }
         
        father[source] = source;
        que.push_back(source);
 
        srand(time(NULL));
        while (que.size() and father[sink] == notVisited) {
            int ind = rand() % que.size();
            int nod = que[ind];
            que[ind] = que[que.size() - 1]; que.pop_back();
            for (auto itr : edgeId[nod]) {
                if (father[edges[itr].other(nod)] == notVisited and edges[itr].getMaxFlow(nod)) {
                    father[edges[itr].other(nod)] = itr;
                    que.push_back(edges[itr].other(nod));
                }
            }
        }
 
        if (father[sink] == notVisited) {
            return 0;
        }
             
        int mxFlow = inf;
        for (int nod = sink; nod != source; nod = edges[father[nod]].other(nod)) {
            mxFlow = min(mxFlow, edges[father[nod]].getReverseMaxFlow(nod));
        }
 
        for (int nod = sink; nod != source; nod = edges[father[nod]].other(nod)) {
            edges[father[nod]].pumpReverseFlow(nod, mxFlow);
        }
 
        return mxFlow;
    }
 
    int getFlow() {
        int actFlow = 0;
        do {
            actFlow = pumpFlow();
            flow += actFlow;
        } while (actFlow != 0);
        return flow;
    }
} flow;
 
int Flow::inf = 0x3f3f3f3f;
 
int main() {
    int n, m; fin >> n >> m;
    flow = Flow(1, n, n);
    while (m--) {
        int a, b, f; fin >> a >> b >> f;
        flow.addEdge(a, b, f);
    }
    fout << flow.getFlow() << '\n';
    return 0;
}