// https://www.infoarena.ro/problema/maxflow

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <deque>
#include <queue>
#include <fstream>
#include <algorithm>

using namespace std;


class Graph
{
private:
    static const int MAX_VERTICES = 1000;
    static const int MAX_EDGES = 5000;

    int noVertices;
    int noEdges;

    vector<vector<int>> neighbours;
    vector<vector<int>> capacity;
    vector<vector<int>> flow;

public:
    Graph(const int &noVertices, const int &noEdges)
        : noVertices(noVertices), noEdges(noEdges),
          neighbours(noVertices + 1),
          capacity(noVertices + 1, vector<int>(noVertices + 1, 0)),
          flow(noVertices + 1, vector<int>(noVertices + 1, 0))
    {
    }

    int getNoVertices()
    {
        return noVertices;
    }

    int getNoEdges()
    {
        return noEdges;
    }


    void addNeighbour(const int& vertex, const int& neighbour_to_add, const int& capacity)
    {
        neighbours[vertex].push_back(neighbour_to_add);
        neighbours[neighbour_to_add].push_back(vertex);

        this->capacity[vertex][neighbour_to_add] = capacity;
    }


    bool BFS(const int& source, const int& sink, vector<int>& parent)
    {
        parent = vector<int> (noVertices + 1, -2);

        queue<int> que;
        que.push(source);
        parent[source] = -1;

        while (!que.empty())
        {
            int curr_vertex = que.front();
            que.pop();

            if (curr_vertex == sink)
                continue;

            for (int neigh : neighbours[curr_vertex])
            {
                //atunci cand avem muchia inversa, capacitatea este 0
                //deci cand flow-ul este 0, nu putem "intoarce" pe acolo ceva
                //cand flow-ul este diferit de 0 (adica negativ) putem intoarce pe acolo ceva
                if (parent[neigh] != -2 || flow[curr_vertex][neigh] == capacity[curr_vertex][neigh])
                    continue;

                parent[neigh] = curr_vertex;
                que.push(neigh);
            }
        }

        return parent[sink] != -2;

    }

    int getMaxFlow(const int& source, const int& sink)
    {
        int maxFlow = 0;
        vector<int> parent;

        while(BFS(source, sink, parent))
        {
            for (int neigh : neighbours[sink])
            {
                int minFlowPath = INT_MAX;

                int curr_vertex = sink;
                int curr_parent = neigh;

                for ( ; curr_vertex != source; curr_vertex = curr_parent, curr_parent = parent[curr_vertex])
                {
                    if (curr_parent == -2)
                    {
                        minFlowPath = 0;
                        break;
                    }

                    //de remarcat ca atunci cand avem o muchie de intoarcere, diferenta o sa fie 
                    //0 - (un flux negativ), deci o sa comparam in continuare cu un numar pozitiv
                    if (capacity[curr_parent][curr_vertex] - flow[curr_parent][curr_vertex] < minFlowPath)
                        minFlowPath = capacity[curr_parent][curr_vertex] - flow[curr_parent][curr_vertex];
                }
                if (minFlowPath == 0)
                    continue;

                maxFlow += minFlowPath;

                curr_vertex = sink;
                curr_parent = neigh;
                for ( ; curr_vertex != source; curr_vertex = curr_parent, curr_parent = parent[curr_vertex])
                {
                    flow[curr_parent][curr_vertex] += minFlowPath;
                    flow[curr_vertex][curr_parent] -= minFlowPath;
                }
            }
        }

        return maxFlow;
    }


};



int main()
{
    int N, M;

    ifstream fin ("maxflow.in");
    fin>> N >> M;
    Graph graph(N, M);

    for (int i=1; i<=M; i++)
    {
        int left, right, capacity;
        fin >> left >> right >> capacity;

        graph.addNeighbour(left, right, capacity);
    }
    
    fin.close();

    ofstream fout("maxflow.out");
    fout << graph.getMaxFlow(1, N) << "\n";

    fout.close();

    return 0;
}