#include <fstream>
#include <vector>
#include <queue>
#include <cassert>
#include <algorithm>
#define ll long long
using namespace std;

const int NMAX = 1000;
const int MMAX = 5000;
const int INF = 1e9;

struct edge
{
    int a, b, cap, f;
    int comp;
    bool org;
};

vector <pair <int, int> > g[NMAX + 1];

edge v[2 * MMAX + 1];


bool viz[NMAX + 1];
int mn[NMAX + 1];
int tata[NMAX + 1];
int what[NMAX + 1]; //muchia de la nod la ta-su din bfs
int n, m;

int lvl[NMAX + 1];

bool exists;


void dfs_aug(int nod)
{
    viz[nod] = 1;
    for (pair <int, int> x : g[nod])
        if (!viz[x.first] and lvl[x.first] == lvl[nod] + 1
            and v[x.second].cap != v[x.second].f)
        {
            tata[x.first] = nod;
            what[x.first] = x.second;
            int pump = v[x.second].cap - v[x.second].f;
            mn[x.first] = min(mn[nod], pump);
            dfs_aug(x.first);
        }
}

queue <int> q;

void augmentpath()
{
    int i;
    for (i = 1; i <= n; i++)
    {
        viz[i] = 0;
        lvl[i] = 0;
        mn[i] = INF;
    }
    q.push(1);
    lvl[1] = 1;
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        for (pair <int, int> x : g[f])
            if (lvl[x.first] == 0 and v[x.second].cap != v[x.second].f)
            {
                lvl[x.first] = lvl[f] + 1;
                q.push(x.first);
            }
    }
    exists = lvl[n];
    if (exists)
    {
        dfs_aug(1);
    }
}

signed main()
{
    ifstream cin("ciorna.in");
    ofstream cout("ciorna.out");
    int i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[2 * i - 1] = {a, b, c, 0, 2 * i, 1};
        v[2 * i] = {b, a, c, c, 2 * i - 1, 0};

        g[a].push_back({b, 2 * i - 1});
        g[b].push_back({a, 2 * i});
    }
    exists = 0;
    augmentpath();
    int flow = 0;
    while (exists)
    {
        int val = mn[n];
        flow += val;
        for (i = n; i != 0; i = tata[i])
        {
            v[what[i]].f += val;
            v[v[what[i]].comp].f -= val;
        }
        augmentpath();
    }
    cout << flow;
}