// unoptimized Edmonds-Karp, compute BFS each time we search for an augmented path.
// should get 70/100
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main(void) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  freopen("maxflow.in", "r", stdin);
  freopen("maxflow.out", "w", stdout);

  int N, M;
  cin >> N >> M;
  vector<int> nxt(2*M+1), head(N), from(2*M+1), to(2*M+1), cap(2*M+1, 0), fl(2*M+1, 0);
  int cnte = 0;
  auto reve = [&M](int e)->int{ return 2*M+1 - e; };
  auto add_edge = [&](int u, int v, int cc)->void{
    cnte++;
    // direct edge
    nxt[cnte] = head[u];
    head[u] = cnte;
    to[cnte] = v;
    from[cnte] = u;
    cap[cnte] = cc;

    // reverse edge
    int re = reve(cnte);
    nxt[re] = head[v];
    head[v] = re;
    to[re] = u;
    from[re] = v;
  };
  for(int i = 0; i < M; i++) {
    int u, v, cc;
    cin >> u >> v >> cc;
    --u, --v;
    add_edge(u, v, cc);
  }

  vector<int> par(N); // edge coming from parent in the BFS tree
  vector<bool> vis(N, 0);
  int src = 0, dest = N-1;
  auto BFS = [&]()->bool {
    fill(vis.begin(), vis.end(), 0);
    queue<int> Q;
    Q.push(src);
    vis[src] = 1;
    while(!Q.empty()) {
      int nod = Q.front(); Q.pop();
      for(int e = head[nod]; e; e = nxt[e]) {
        int nbr = to[e];
        if (!vis[nbr] && fl[e] < cap[e]) {
          par[nbr] = e;
          Q.push(nbr);
          vis[nbr] = 1;
          if (nbr == dest) return 1;
        }
      }
    }
    return 0;
  };
  auto dbg = [&](){
    cout << string(20,'-') << "forward graph" << string(20, '-') << endl;
    for(int e = 1; e <= M; e++) {
      cout << from[e]+1 << "->" << to[e]+1 << ": " << fl[e] << "/" << cap[e] << endl;
    }
    cout << string(20,'-') << "residue graph" << string(20, '-') << endl;
    for(int e = 1; e <= M; e++) {
      int re = reve(e);
      cout << from[re]+1 << "->" << to[re]+1 << ": " << fl[re] << "/" << cap[re] << endl;
    }
    cout << string(20,'-') << "BFS TREE" << string(20, '-') << endl;
    stack<int> edges;
    for(int nod = dest; par[nod]; nod = from[par[nod]]) {
      edges.push(par[nod]);
    }
    while(!edges.empty()) {
      int e = edges.top(); edges.pop();
      cout << from[e] + 1 << "->" << to[e] +1<< ": " << fl[e] << "/" << cap[e] << endl;
    }
  };
  const int INF = 1e6;
  int flow, fmin;
  for(flow = 0; BFS(); flow += fmin) {
    fmin = INF;
    for(int nod = dest; nod != src; nod = from[par[nod]]) {
      int e = par[nod];
      fmin = min(fmin, cap[e] - fl[e]);
    }
    for(int nod = dest; nod != src; nod = from[par[nod]]) {
      int e = par[nod];
      fl[e] += fmin;
      fl[reve(e)] -= fmin;
    }
    // dbg();
  }
  cout << flow << "\n";

  return 0;
}