/* 4. Ciclu eulerian cu un nod fals pentru a distinge ciclurile euleriene disjuncte
  (nu merge infoarena asa ca link catre submisia veche) : https://www.infoarena.ro/job_detail/2528389?action=view-source
 */
#include <fstream>
#include <vector>
#include <iostream>
#include <bitset>
#include <queue>
using namespace std;

const short N = 1001;

bitset <N> vis;
int capacity[N][N], maxflow;
short n, from[N], start, finish;
vector <short> L[N];

bool BFS()
{
    int curr;
    queue<int> q;
    vis.reset();
    for (int i = 1; i <= n; i++)
    {
        q.push(start);
        vis[start] = 1;
        while (!q.empty())
        {
            curr = q.front();
            q.pop();
            for (short& next : L[curr])
                if (capacity[curr][next] != 0 && !vis[next])
                {
                    from[next] = curr;
                    if (next == finish)
                        return true;
                    vis[next] = true;
                    q.push(next);
                }
        }
    }
    return false;
}

void MaxFlow()
{
    int curr, prev, flow;
    while(BFS())
    {
        curr = finish, flow = 2e9;
        while (curr != start)
        {
            prev = from[curr];
            flow = min(flow, capacity[prev][curr]);
            curr = prev;
        }
        curr = finish;
        while (curr != start)
        {
            prev = from[curr];
            capacity[prev][curr] -= flow;
            capacity[curr][prev] += flow;
            curr = prev;
        }
        maxflow += flow;
    }
    ofstream fout ("maxflow.out");
    fout << maxflow << "\n";
    fout.close();
}

void Read()
{
    short m, x, y;
    int c;
    ifstream fin ("maxflow.in");
    fin >> n >> m;
    start = 1, finish = n;
    from[start] = -1;
    while (m--)
    {
        fin >> x >> y >> c;
        L[x].push_back(y);
        L[y].push_back(x);
        capacity[x][y] = c;
    }
    fin.close();
}

int main()
{
    Read();
    MaxFlow();
    return 0;
}