#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

class Flow
{
    int source, sink;
    int n;
    std::vector<bool> visited;
    std::vector<std::vector<int> > graph;
//    std::vector<std::vector<int> > capacity;
    std::vector<std::vector<int> > flow;
    std::vector<int> father;

    void dfs(int x) {
        visited[x] = true;
        for (int node : graph[x]) {
            if (!visited[node] && flow[x][node] > 0) {
                dfs(node);
            }
        }
    }

    bool bfs()
    {
        visited.assign(n+1, false);
        std::queue<int> q;
        q.push(source);
        visited[source] = true;

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

            for(int neighbour : graph[node])
            {
                if(!visited[neighbour] && flow[node][neighbour] > 0) {
                    visited[neighbour] = true;
                    q.push(neighbour);
                    father[neighbour] = node;
                    if (neighbour == sink)
                        return true;
                }
            }
        }
        return false;
    }

public:
    Flow(int n, int source, int sink)
    {
        this->source = source;
        this->sink = sink;
        this->n = n;
//        capacity.resize(n + 1, std::vector<int>(n + 1));
        flow.resize(n + 1, std::vector<int>(n + 1));
        graph.resize(n + 1);
        visited.resize(n + 1);
        father.resize(n + 1);
    }

    void addEdge(int x, int y, int c)
    {
        if(flow[x][y] == 0)
        {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        flow[x][y] += c;
    }

    int getMaxFlow()
    {
        int maxFlow = 0;
        do{
            if( !bfs() )
                break;
            for (auto nod : graph[n]) {
                if(!flow[nod][n] || !visited[nod])
                    continue;

                father[n] = nod;
                int flowMin = 0x7fffffff;
                for (int i = n; father[i] != 0; i = father[i]) {
                    flowMin = std::min(flowMin, flow[father[i]][i]);
                }
                if (flowMin == 0)
                    continue;

                maxFlow += flowMin;
                for (int i = n; father[i] != 0; i = father[i]) {
                    flow[father[i]][i] -= flowMin;
                    flow[i][father[i]] += flowMin;
                }
            }
        } while (true);
        return maxFlow;
    }

    std::vector<std::pair<int, int>> getMinCut()
    {
        visited.assign(n+1, false);
        dfs(source);
        std::vector<std::pair<int, int>> minCut;
        for (int i = 1; i <= n; ++i) {
            for (int j : graph[i]) {
                if (visited[i] && !visited[j] && flow[i][j] > 0)
                    minCut.emplace_back(i, j);
            }
        }
        return minCut;
    }
};

int main()
{
    std::ifstream in("maxflow.in");
    int n, m;
    in >> n >> m;
    Flow gr(n, 1, n);
    int x, y, z;
    while(m--)
    {
        in >> x >> y >> z;
        gr.addEdge(x, y, z);
    }
    in.close();
    int rasp = gr.getMaxFlow();
    std::ofstream out("maxflow.out");
    out << rasp;
    out.close();
    return 0;
}