#include <bits/stdc++.h>
#define Nmax 1005
#define INF 200000
using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int N, M, S, D;
vector<int> G[Nmax];
vector<pair<int, int> > nodes;
bool vis[Nmax];
int f[Nmax][Nmax], c[Nmax][Nmax], father[Nmax], Min[Nmax];
deque<int> Q;

void updateFlow() {
      memset(vis, 0, sizeof(vis));
   for (auto it: nodes) {
       int curr = it.first, flow = it.second;
       while (curr != S) {
            int nxt = father[curr];
            f[nxt][curr] += flow, f[curr][nxt] -= flow;
            curr = nxt;
       }
   }
}

int MakeFlow() {
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    memset(Min, INF, sizeof(Min));
    nodes.clear();
    Q.push_back(S);
    vis[S] = 1;

    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop_front();
        for (auto nxt: G[curr])
        if (f[curr][nxt] < c[curr][nxt] && !vis[nxt]) {
            if (nxt != D) {
                Q.push_back(nxt);
                father[nxt] = curr;
                vis[nxt] = 1;
                Min[nxt] = min(Min[curr], c[curr][nxt] - f[curr][nxt]);
            }
            else {
                 Min[nxt] = min(Min[curr], c[curr][D] - f[curr][D]);
                 nodes.push_back(make_pair(curr, Min[nxt]));
                 ans += Min[nxt];
                 f[curr][D] += Min[nxt], f[D][curr] -= Min[nxt];
                 while (!Q.empty() && (Q.back() == curr || father[Q.back()] == curr))
                       Q.pop_back();
                 break;
            }
    }
    }
    return ans;
}
int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        c[x][y] = z;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    S = 1, D = N;

    int ans = 0;
    bool ok = 1;
    while (ok) {
        int res = MakeFlow();
        if (res) ans += res, updateFlow();
        else ok = 0;
    }
       fout << ans << '\n';
    return 0;
}