#include <bits/stdc++.h>
#define NMAX 1005
#define INF 10000000000
using namespace std;
ifstream f ("maxflow.in");
ofstream g ("maxflow.out");
int C[NMAX][NMAX], F[NMAX][NMAX], father[NMAX], n, m, v[NMAX], flow;
bitset < NMAX > b;
vector < int > a[NMAX];

bool BF ()
{
    v[0] = v[1] = 1;
    b.reset();
    b[1] = 1;
    for (int i = 1; i <= v[0]; i++)
    {
        int nod = v[i];
        if (nod == n) continue;
        for (int j = 0; j < a[nod].size(); j++)
        {
            int next = a[nod][j];
            if (C[nod][next] == F[nod][next] || b[next]) continue;
            b[next] = 1;
            v[++v[0]] = next;
            father[next] = nod;
        }
    }
    cout<<b[n]<<' ';
    return b[n];
}

int main()
{
    f>>n>>m;
    while (m--)
    {
        int x, y, z;
        f>>x>>y>>z;
        a[x].push_back(y);
        a[y].push_back(x);
        C[x][y] += z;
    }
    for (flow = 0; BF();)
        for (int i = 0; i < a[n].size(); i++)
        {
            int nod = a[n][i];
            if (F[nod][n] == C[nod][n] || !b[nod]) continue;
            father[n] = nod;
            int fmin = INF;
            for (nod = n; nod != 1; nod = father[nod])
                fmin = min(fmin, C[father[nod]][nod] - F[father[nod]][nod]);
            if (fmin == 0) continue;
            for (nod = n; nod != 1; nod = father[nod])
            {
                F[father[nod]][nod] += fmin;
                F[nod][father[nod]] -= fmin;
            }
            flow += fmin;
        }
    g<<flow;
    return 0;
}