#include <iostream>
#include <vector>
#include <deque>
using namespace std;


int s, t;
const int M_N = 699;
const int INF = 1000000;
const long long INF_FLOW = 1000000000;

struct edge
{
    int next, capacity, flow;
    edge *back_edge;

    edge(int next, int capacity) : next(next), capacity(capacity), flow(0) {}

    int getCap()
    {
        return capacity - flow;
    }
};

vector<edge *> g[M_N];
vector<int> d(M_N);
vector<int> p(M_N);


void fill_graph(int m)
{
    int v1, v2, cost;
    for (int i = 0; i < m; i++)
    {
        cin >> v1 >> v2 >> cost;

        edge *e = new edge(v2, cost), *b_e = new edge(v1, 0);
        e->back_edge = b_e;
        b_e->back_edge = e;

        g[v1].push_back(e);
        g[v2].push_back(b_e);
    }
}


bool bfs(int c) {
    d.assign(M_N, INF);
    d[s] = 0;

    deque<int> dq;
    dq.push_back(s);

    while (!dq.empty())
    {
        int v = dq.front();
        dq.pop_front();

        for (edge *edge : g[v])
        {
            if (d[edge->next] == INF && edge->getCap() >= c)
            {
                d[edge->next] = d[v] + 1;
                dq.push_back(edge->next);
            }
        }
    }
    return d[t] != INF;
}

int dfs(int v, int flow)
{
    if (v == t)
    {
        return flow;
    }
    if (flow == 0)
    {
        return 0;
    }
    for (int i = p[v]; i < g[v].size(); ++i)
    {
        edge *edge = g[v][i];

        if (d[edge->next] != d[v] + 1)
            continue;

        int flow_f;
        if (flow_f = dfs(edge->next, min(edge->getCap(), flow))) {
            edge->flow += flow_f;
            edge->back_edge->flow -= flow_f;

            return flow_f;
        }
        p[v]++;
    }

   return 0;
}

long long alg_dinic(int c)
{
    long long flow = 0;
    while (bfs(c) > 0) {
        p.assign(M_N, 0);
        long long temp_flow;
        while (temp_flow = dfs(1, INF_FLOW))
        {
            flow += temp_flow;
        }
    }

    return flow;
}

long long find_max_flow(int m_c, long m_f)
{
        while (m_c) {
        m_f += alg_dinic(m_c);
        m_c /= 2;
    }
    return m_f;
}

int main() {
    int n, m;
    cin >> n >> m;

    fill_graph(m);

    s = 1, t = n;

    int max_c = INF_FLOW;
    long long max_f = 0;


    cout << find_max_flow(max_c, max_f)<< endl;

    return 0;
}