#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <string>

struct Edge {
    int a, b, capacity, flow;
};

class MaxFlow
{
private:
    const int INF = 1000000000;
    int vertexCount;
    std::vector<Edge> edges;
    std::vector<std::vector<int>> g;
    int * q;
    int * d;
    int * ptr;
    int s;
    int t;
public:
    MaxFlow(std::string fileName)
    {
        int m, a, b, c;
        std::ifstream in(fileName, std::ios::in);
        in >> vertexCount;
        in >> m;
        g.assign(vertexCount, std::vector<int>());
        q = new int[vertexCount];
        d = new int[vertexCount];
        ptr = new int[vertexCount];
        for (size_t i = 0; i < vertexCount; i++)
        {
            in >> a >> b >> c;
            addEdge(a - 1, b - 1, c);
        }
        in.close();
    }

    void addEdge(int a, int b, int capacity)
    {
        Edge e1 = { a, b, capacity, 0 };
        Edge e2 = { b, a, 0, 0 };
        g[a].push_back(edges.size());
        edges.push_back(e1);
        g[b].push_back(edges.size());
        edges.push_back(e2);
    }

    bool BFS()
    {
        int qh = 0;
        int qt = 0;
        q[qt++] = s;
        memset(d, -1, vertexCount * sizeof(d[0]));
        d[s] = 0;
        while (qh < qt && d[t] == -1) {
            int v = q[qh++];
            for (size_t i = 0; i<g[v].size(); ++i) {
                int id = g[v][i],
                    to = edges[id].b;
                if (d[to] == -1 && edges[id].flow < edges[id].capacity) {
                    q[qt++] = to;
                    d[to] = d[v] + 1;
                }
            }
        }
        return d[t] != -1;
    }
    int min(int a, int b)
    {
        return (a < b ? a : b);
    }
    int dfs(int v, int flow) {
        if (!flow)  return 0;
        if (v == t)  return flow;
        for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
            int id = g[v][ptr[v]],
                to = edges[id].b;
            if (d[to] != d[v] + 1)  continue;
            int pushed = dfs(to, min(flow, edges[id].capacity - edges[id].flow));
            if (pushed) {
                edges[id].flow += pushed;
                edges[id ^ 1].flow -= pushed;
                return pushed;
            }
        }
        return 0;
    }

    int Dinic(int s, int t)
    {
        this->s = s;
        this->t = t;
        int flow = 0;
        for (;;) {
            if (!BFS())  break;
            memset(ptr, 0, vertexCount * sizeof ptr[0]);
            while (int pushed = dfs(s, INF))
                flow += pushed;
        }
        return flow;
    }
    int vertexSize()
    {
        return this->vertexCount;
    }

};

void main()
{
    MaxFlow* mf = new MaxFlow("maxflow.in");
    std::ofstream out("maxflow.out", std::ios::out);
    out << mf->Dinic(0, mf->vertexSize() - 1) + 1;
    out.close();
}