#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a) begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

#define FF first
#define SS second

template <class S, class T>
istream& operator>>(istream& is, pair<S, T>& p) {
  return is >> p.FF >> p.SS;
}
template <class T>
istream& operator>>(istream& is, vector<T>& xs) {
  for (auto& x : xs) is >> x;
  return is;
}
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  return os << p.FF << " " << p.SS;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& xs) {
  for (unsigned int i = 0; i < xs.size(); ++i) os << (i ? " " : "") << xs[i];
  return os;
}
template <class T>
void maxi(T& x, T y) {
  if (x < y) x = y;
}
template <class T>
void mini(T& x, T y) {
  if (x > y) x = y;
}
void debug(istringstream&) {}
template <char sep = ',', class Head, class... Tail>
void debug(istringstream& iss, Head&& head, Tail&&... tail) {
  string name;
  getline(iss, name, ',');
  cout << sep << name << "=" << head;
  debug(iss, forward<Tail>(tail)...);
}

#ifdef PYONPOI
#define DEBUG(...)                  \
  do {                              \
    istringstream ss(#__VA_ARGS__); \
    debug<' '>(ss, __VA_ARGS__);    \
    cout << endl;                   \
  } while (0)
#else
#define DEBUG
#endif
void init_io(int argc, char* argv[]) {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
#ifdef PYONPOI
  if (argc > 1) {
    ifstream* ifs = new ifstream();
    ifs->open(argv[1]);
    cin.rdbuf(ifs->rdbuf());
  }
#endif
}

const double EPS = 1e-10;
const double PI = acos(-1.0);
const LL MOD = 1e9 + 7;

template<typename T>
struct FlowNetwork {
  struct Edge {
    int from;
    int to;
    T cap;
    int rev_id;
    bool fwd;
  };

  int V, E, src, dst;
  VI height;
  vector<T> exceed;

  vector<vector<Edge>> edge;

  FlowNetwork(int V, int src, int dst) : V (V), src(src), dst(dst) {
    edge.resize(V);
    height.assign(V, 0);
    exceed.assign(V, T{0});
  };

  void AddEdge(int u, int v, T cap) {
    edge[u].push_back(Edge{u, v, cap, SZ(edge[v]), true});
    edge[v].push_back(Edge{v, u, 0, SZ(edge[u]) - 1, false});
  }

  void push(Edge& e, T f) {
    int u = e.from;
    int v = e.to;
    auto& rev_e = edge[v][e.rev_id];

    e.cap -= f; 
    rev_e.cap += f;

    exceed[u] -= f;
    exceed[v] += f;
  }

  
  string id (int v) {
    if (v == src) return "S";
    if (v == dst) return "T";
    return (V <= 26 ? string(1, 'a' + v) : to_string(v + 1));
  };

  string DumpDot(string msg = "") {
    string txt = "";

    txt +=
        "digraph graph_name {\n"
        "  graph [\n"
        "    bgcolor = \"#ffffffff\",\n"
        "    fontcolor = red,\n"
        "    labelloc = \"t\",\n"
        "    labeljust = \"c\",\n"
        "    label=\"" + msg + "\",\n"
        "    style = filled,\n"
        "    rankdir = TB\n"
        "  ];\n";

    txt +=
        "  node [\n"
        "    shape = ellipse,\n"
        "    style = filled,\n"
        "    colorscheme = rdylgn11,\n"
        "    fontname = \"Migu 1M\",\n"
        "    color = 7,\n"
        "    fontsize = 18,\n"
        "    fontcolor = 6,\n"
        "    fillcolor = 11,\n"
        "    margin = 0.07\n"
        "  ];\n";

    txt +=
        "  edge [\n"
        "    colorscheme = rdylgn11,\n"
        "  ];\n";

    // height
    int max_h = 2 * V;
    for (int h = max_h; h >= 0; --h) {
      txt += (h < max_h ? ", " : "") + to_string(h);
    }
    txt += " [ shape=box3d ];\n";

    for (int h = max_h; h >= 0; --h) {
      txt += (h < max_h ? "->" : "") + to_string(h);
    }
    txt += " [ style=invis ];\n";

    // vertices
    for (int v = 0; v < V; ++v) {
      txt += (v ? ", " : "") + id(v);
    }
    txt += ";\n";
    for (int v = 0; v < V; ++v) {
      txt += id(v) + "[label = \"" + id(v) + "(" + to_string(exceed[v]) + ")\"]" + ";\n";
    }

    // edges
    for (int v = 0; v < V; ++v) {
      for (auto& e : edge[v]) {
        if (e.cap == 0) continue;
        stringstream ss;

        ss
          << id(e.from) << "->" << id(e.to)
          << "[ label=" << e.cap << ";"
          << " style=" << (e.fwd ? "solid" : "dashed") << ";"
          << "fontcolor=" << (e.fwd ? "\"#000000\"" : "\"#222222\"") << ";"
          << "color=" << (e.fwd ? 9 : 3) << ";];";

        txt += ss.str() + "\n";
      }
    }

    // height
    for (int v = 0; v<V;++v){
      int h = height[v];
      txt += "{  rank=same;" + to_string(h) + "; " + id(v) + "}\n";
    }

    txt += "}\n";
    return txt;
  };
};

template<typename T>
void initialize(FlowNetwork<T>& G) {
  G.height[G.src] = G.V;
  
  for (auto& e: G.edge[G.src]) {
    T f = e.cap;
    G.push(e, f);
  }
}

template<typename T>
T max_flow(FlowNetwork<T>& G, bool debug = false) {
  int cnter = 1;
  auto save = [&](const string& msg){
    if (!debug) return;

    stringstream ss;
    ss << "dump_" << setfill('0') << setw(5) << cnter << ".dot";
    ofstream ofs(ss.str());
    ofs << G.DumpDot(msg);
    ++cnter;
  };

  auto push = [&] (typename FlowNetwork<T>::Edge& e) {
    int u = e.from;

    T delta = min(e.cap, G.exceed[u]);
    G.push(e, delta);
    save("push(" + G.id(e.from) + ", " + G.id(e.to) + ")");
  };

  auto relabel = [&] (int u) {
    int mn = 3 * G.V;
    for (auto& e : G.edge[u]) {
      if (e.cap > 0)
        mn = min(mn, G.height[e.to]);
    }
    G.height[u] = 1 + mn;
    save("relabel(" + G.id(u) + ")");
  };

  vector<int> iter(G.V, 0);
  auto discharge = [&] (int u) {
    while (G.exceed[u] > 0) {
      int i = iter[u];
      if (i == SZ(G.edge[u])) {
        relabel(u);
        iter[u] = 0;
      }
      else {
        auto& e = G.edge[u][i];
        if (e.cap > 0 && G.height[e.from] == G.height[e.to] + 1) {
          push(e);
        }
        else {
          ++iter[u];
        }
      }
    }
  };

  initialize(G);
  list<int> L;
  for (int i=0; i<G.V;++i){
    if (i == G.src || i == G.dst) continue;
    L.push_front(i);
  }

  auto it = begin(L);
  while (it != end(L)) {
    int u = *it;
    int old_height = G.height[u];

    discharge(u);
    if (G.height[u] > old_height) {
      L.erase(it);
      L.push_front(u);
      it = begin(L);
    }
    ++it;
  }

  return G.exceed[G.dst];
}

int main(int argc, char* argv[]) {
  init_io(argc, argv);

  int V, E;
  cin >> V >> E;

  FlowNetwork<int> G(V, 0, V-1);
  REP(i,E) {
    int u, v, cap;
    cin >> u >> v >> cap;

    G.AddEdge(u, v, cap);
  }


  int mf = max_flow(G, false);
  cout << mf << endl;

  return 0;
}



Measured memory_bytes: 3364