#include <fstream>
#include <vector>
#include <queue>
using namespace std;
 
#define min(x,y) ((x < y) ? x : y)
#define N 1005
#define add push_back
 
typedef unsigned u;
 
ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");
 
queue <int> Q;
vector <int> g[N], t(N, 0), viz(N, 0);
int c[N][N], f[N][N], vizit, n, m, sol;
 
int bfs () {
    Q.push(1);
    viz[1] = vizit;
    while (Q.size()) {
        int x = Q.front();
        Q.pop();
        for (u i = 0; i < g[x].size(); ++i) {
            int y = g[x][i];
            if (f[x][y] < c[x][y] && viz[y] < vizit) {
                Q.push (y);
                t[y] = x;
                viz[y] = vizit;
            }
        }
    }
    return viz[n];
}
                 
         
 
int main() {
    fin >> n >> m;
    while (m--) {
        int x, y, C;
        fin >> x >> y >> C;
        g[x].add(y);
        g[y].add(x);
        c[x][y] = C;
    }
    fin.close();
    while (++vizit == bfs())
        for (int i = 1; i < n; ++i)
            if (f[i][n] < c[i][n]) {
                int MIN = c[i][n] - f[i][n], x = i;
                while (x != 1) {
                    MIN = min (c[t[x]][x] - f[t[x]][x], MIN);
                    x = t[x];
                }
                sol += MIN;
                f[i][n] += MIN;
                f[n][i] -= MIN;
                x = i;
                while (x != 1) {
                    f[t[x]][x] += MIN;
                    f[x][t[x]] -= MIN;
                    x = t[x];
                }
            }
    fout << sol;
    fout.close();
}