#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stdlib.h>
using namespace std;

const int N = 1201;

int n, poz, s = 1, d = n;
char a[10000];
vector<int> v[N];
int cap[N][N], f[N][N], p[N];
bool ver[N];

bool bfs() {
    queue<int> q;
    int i;

    for(i =0; i < N; ++i) {
        p[i] = 0;
        ver[i] = 0;
    }

    p[s] = s;
    ver[s] = 1;
    q.push(s);

    while(!q.empty()) {
        int el = q.front();
        q.pop();

        for(vector<int>::iterator it = v[el].begin(); it != v[el].end(); ++it)
            if(!ver[*it] && cap[el][*it] - f[el][*it] > 0) {
                ver[*it] = 1;

                q.push(*it);

                p[*it] = el;
            }
    }

    return p[n];
}

int flux() {
    int i, j, rez = 0;

    while(bfs())
        for(i = 1; i <= n; ++i) if(i != d)
            if(cap[i][d] - f[i][d] > 0 && p[i]) {
                int smin = cap[i][d] - f[i][d];

                for(j = i; j != s; j = p[j])
                    smin = min(smin, cap[p[j]][j] - f[p[j]][j]);

                f[i][d] += smin;
                f[d][i] -= smin;

                for(j = i; j != s; j = p[j]) {
                    f[p[j]][j] += smin;
                    f[j][p[j]] -= smin;
                }

                rez += smin;
            }
    return rez;
}

int main() {
    int i;
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);

    int nu = 1, m;


        cin >> n >> m;
        d = n;
        if(n == 0)
            return 0;

        for(i = 1; i <= m; ++i) {
            int a, b, c;
            cin >> a >> b >> c;

            cap[a][b] += c;
            //cap[b][a] += c;

            v[a].push_back(b);
            v[b].push_back(a);
        }


        cout << flux();
        ++nu;

        memset(cap, 0, sizeof(cap));
        memset(f, 0, sizeof(f));
        for(int i = 0; i < N; ++i)
            v[i].clear();



    return 0;
}