/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-04-08 15:20:46
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) { os << '{'; for (auto it = mp.begin(); it != mp.end(); ++it) { os << '{' << it->first << ':' << it->second << '}'; if (it != --mp.end()) os << ','; } os << '}'; return os; }
template<class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& st) { os << '{'; for (auto it = st.begin(); it != st.end(); ++it) { os << *it; if (it != --st.end()) os << ','; } os << '}'; return os; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

template <class _Tp>
class Dinic {
 public:
  Dinic(int node_size) : node_size_(node_size) { initialize(); }

  void add(int from, int to, _Tp cost) {
    assert(0 <= from && from < node_size_ && 0 <= to && to < node_size_);
    graph_[from].emplace_back((edge) {to, cost, static_cast<int>(graph_[to].size())});
    graph_[to].emplace_back((edge)
        {from, static_cast<_Tp>(0), static_cast<int>(graph_[from].size()) - 1});
  }

  _Tp max_flow(int s, int t) {
    _Tp flow = 0;
    for (;;) {
      bfs(s);
      if (level_[t] < 0) return flow;
      std::fill(iter_.begin(), iter_.end(), 0);
      _Tp f;
      while ((f = dfs(s, t, std::numeric_limits<_Tp>::max() / static_cast<_Tp>(2))) > 0) {
        flow += f;
      }
    }
  }

 private:
  struct edge {
    int to;
    _Tp cap;
    int rev;
  };
  int node_size_;
  std::vector<std::vector<edge>> graph_;
  std::vector<int> level_;
  std::vector<int> iter_;

  void initialize() {
    graph_.resize(node_size_);
    level_.assign(node_size_, 0);
    iter_.assign(node_size_, 0);
  }

  void bfs(int s) {
    std::fill(level_.begin(), level_.end(), -1);
    std::queue<int> que;
    level_[s] = 0;
    que.emplace(s);
    while (!que.empty()) {
      int cur = que.front();
      que.pop();
      for (const edge& next : graph_[cur]) {
        if (next.cap > 0 && level_[next.to] < 0) {
          level_[next.to] = level_[cur] + 1;
          que.emplace(next.to);
        }
      }
    }
  }

  _Tp dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int& i = iter_[v]; i < (int) graph_[v].size(); ++i) {
      edge& e = graph_[v][i];
      if (e.cap > 0 && level_[v] < level_[e.to]) {
        _Tp d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          graph_[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
};

void GRL_6_A() {
  int n, m; cin >> n >> m;
  Dinic<int> dinic(n);
  for (int i = 0; i < m; ++i) {
    int u, v, c; cin >> u >> v >> c;
    dinic.add(u, v, c);
  }
  cout << dinic.max_flow(0, n - 1) << '\n';
}

void ARC092_A() {
  int n; cin >> n;
  vector<int> a(n), b(n), c(n), d(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  for (int i = 0; i < n; ++i) {
    cin >> c[i] >> d[i];
  }

  Dinic<int> dinic(2 * n + 2);
  int s = 2 * n, t = 2 * n + 1;

  for (int i = 0; i < n; ++i) {
    dinic.add(s, i, 1);
  }

  for (int i = 0; i < n; ++i) {
    dinic.add(n + i, t, 1);
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (a[i] < c[j] && b[i] < d[j]) {
        dinic.add(i, j + n, 1);
      }
    }
  }

  cout << dinic.max_flow(s, t) << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  GRL_6_A();
  //ARC092_A();

  return 0;
}


Measured memory_bytes: 3264