#include <bits/stdc++.h>

using namespace std;

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

void usain_bolt() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
}

void augmentPath(int n, vector<int>& parents, vector<vector<int>>& c, vector<vector<int>>& flow, int& cnt, bool update = false) {
  int node = n;
  while (node != 1) {
      int parent = parents[node];
      if (update) {
        flow[parent][node] += cnt;
        flow[node][parent] -= cnt;
      } else {
        cnt = min(cnt, c[parent][node] - flow[parent][node]);
      }
      node = parent;
  }
}

void solve()
{
    int n, m;
    fin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<vector<int>> c(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        fin >> x >> y >> w;
        c[x][y] += w;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    vector<vector<int>> flow(n + 1, vector<int>(n + 1, 0));
    auto bfs = [&]() {
        vector<int> parent(n + 1, -1);
        queue<int> q;
        vector<bool> seen(n + 1, false);
        seen[1] = true;
        q.push(1);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            if (node == n) {
                continue;
            }
            for (auto neigh : g[node]) {
                if (seen[neigh] || flow[node][neigh] == c[node][neigh]) {
                    continue;
                }
                seen[neigh] = true;
                q.push(neigh);
                parent[neigh] = node;
            }
        }

        return make_pair(parent, seen);
    };
    int sol = 0;
    while (1) {
        auto [parents, seen] = bfs();
        if (!seen[n]) {
            break;
        }
        for (auto neigh : g[n]) {
            if (flow[neigh][n] == c[neigh][n] || !seen[neigh]) {
                continue;
            }
            parents[n] = neigh;
            int cnt = c[neigh][n] - flow[neigh][n];
            augmentPath(n, parents, c, flow, cnt);
            if (cnt == 0) {
                continue;
            }
            sol += cnt;
            augmentPath(n, parents, c, flow, cnt, true);
        }
    }
    fout << sol << '\n';

    return;
}

int main()
{
  int tt;
  // cin >> tt;
  tt = 1;
  while (tt--)
  {
    solve();
  }

  return 0;
}