#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <unordered_map>

using std::size_t;
using std::vector;
using std::unordered_map;
using std::numeric_limits;
using std::pair;
using std::cin;
using std::cout;
using std::unique_ptr;

typedef long long ll;

template <typename TScalar> struct Edge {
  TScalar capacity_;

  TScalar flow_;
};

template <typename TScalar> class INetworkIteratorInterface {
public:
  virtual explicit operator bool() const = 0;

  virtual void PushFlowWithReversed(TScalar flow) = 0;

  virtual void PushFlow(TScalar flow) = 0;

  virtual size_t From() const = 0;

  virtual size_t To() const = 0;

  virtual TScalar Flow() const = 0;

  virtual TScalar Capacity() const = 0;

  virtual ~INetworkIteratorInterface() = default;

  INetworkIteratorInterface() = default;

  virtual void forward_iterator() = 0;

  virtual std::unique_ptr<INetworkIteratorInterface> clone() const = 0;
};

template <typename TScalar> class INetworkIterator {
private:
  std::unique_ptr<INetworkIteratorInterface<TScalar>> impl;

public:
  explicit operator bool() { return bool(*impl); }

  explicit INetworkIterator(
      std::unique_ptr<INetworkIteratorInterface<TScalar>> r)
      : impl(std::move(r)) {}

  INetworkIterator(const INetworkIterator &r) : impl(r.impl->clone()) {}

  INetworkIterator &operator=(const INetworkIterator &other) {
    impl = std::move(other.impl->clone());
  }

  INetworkIterator &operator++() {
    impl->forward_iterator();
    return *this;
  }

  INetworkIterator operator++(int) {
    INetworkIterator tmp(*this);
    impl->forward_iterator();
    return tmp;
  }

  explicit operator bool() const { return bool(*impl); };

  /*pair<size_t, Edge<TScalar>> operator*() const {
    return *(*impl);
  };*/

  INetworkIteratorInterface<TScalar> *operator->() const { return impl.get(); }
};

template <typename TScalar> class INetwork {
protected:
  size_t source_;

  size_t target_;

public:
  size_t getSource() const { return source_; }

  size_t getTarget() const { return target_; }

  virtual size_t getSize() const = 0;

  virtual INetworkIterator<TScalar> GetForwardIterator(size_t vertex) = 0;

  virtual INetworkIterator<TScalar> GetBackIterator(size_t vertex) = 0;

  virtual void AddEdge(size_t u, size_t v, TScalar c) = 0;

  virtual void AddFlow(size_t u, size_t v, TScalar f) = 0;

  virtual Edge<TScalar> &GetEdge(size_t u, size_t v) = 0;

  INetwork(size_t source_, size_t target_)
      : source_(source_), target_(target_) {}

  virtual ~INetwork() = default;
};

template <typename TScalar> class Network : public INetwork<TScalar> {
private:
  using InnerContainerT = vector<unordered_map<size_t, Edge<TScalar> *>>;
  InnerContainerT inner_network_;
  InnerContainerT inner_network_mirror_;

public:
  size_t getSize() const override { return inner_network_.size(); }

  Edge<TScalar> &GetEdge(size_t u, size_t v) override {
    return *inner_network_[u][v];
  }

  void AddFlow(size_t u, size_t v, TScalar f) override {
    inner_network_[u][v]->flow_ += f;
    inner_network_[v][u]->flow_ -= f;
  }

  Network(size_t source_, size_t target_, size_t n_)
      : INetwork<TScalar>(source_, target_), inner_network_(n_),
        inner_network_mirror_(n_) {}

  template <typename ContainerT>
  class NetworkIterator : public INetworkIteratorInterface<TScalar> {
  private:
    using InnerIterator =
        typename unordered_map<size_t, Edge<TScalar> *>::iterator;

  private:
    InnerIterator my_iterator_;
    size_t from_vertex;
    InnerContainerT &inner_network_;
    bool reversed;

    void forward_iterator() override {
      if (bool(*this))
        ++my_iterator_;
    }

  public:
    unique_ptr<INetworkIteratorInterface<TScalar>> clone() const override {
      return std::make_unique<NetworkIterator>(*this);
    }

    TScalar Flow() const override { return my_iterator_->second->flow_; }

    TScalar Capacity() const override {
      return my_iterator_->second->capacity_;
    }

    size_t To() const override {
      if (reversed)
        return from_vertex;
      return my_iterator_->first;
    }

  public:
    explicit operator bool() const override {
      return my_iterator_ != inner_network_[from_vertex].end();
    }

    void PushFlowWithReversed(TScalar flow) override {
      my_iterator_->second->flow_ += flow;
      if (!reversed)
        inner_network_[my_iterator_->first][from_vertex]->flow_ -= flow;
      else
        inner_network_[from_vertex][my_iterator_->first]->flow_ -= flow;
    }

    void PushFlow(TScalar flow) override {
      my_iterator_->second->flow_ += flow;
    }

    NetworkIterator(const InnerIterator &my_iterator_, size_t from_vertex,
                    InnerContainerT &inner_network_, bool reversed = false)
        : my_iterator_(my_iterator_), from_vertex(from_vertex),
          inner_network_(inner_network_), reversed(reversed) {}

    size_t From() const override {
      if (reversed)
        return my_iterator_->first;
      return from_vertex;
    }
  };

  INetworkIterator<TScalar> GetForwardIterator(size_t vertex) override {
    return INetworkIterator<TScalar>(
        std::unique_ptr<NetworkIterator<TScalar>>(new NetworkIterator<TScalar>(
            inner_network_[vertex].begin(), vertex, inner_network_)));
  }

  INetworkIterator<TScalar> GetBackIterator(size_t vertex) override {
    return INetworkIterator<TScalar>(std::unique_ptr<NetworkIterator<TScalar>>(
        new NetworkIterator<TScalar>(inner_network_mirror_[vertex].begin(),
                                     vertex, inner_network_mirror_, true)));
  }

  void AddEdge(size_t u, size_t v, TScalar c) override {
    if (!inner_network_[u].count(v)) {
      inner_network_[u][v] = new Edge<TScalar>();
      inner_network_[v][u] = new Edge<TScalar>();
    }
    inner_network_[u][v]->capacity_ += c;
    inner_network_[u][v]->flow_ = inner_network_[v][u]->flow_ = 0;
    inner_network_mirror_[u][v] = inner_network_[v][u];
    inner_network_mirror_[v][u] = inner_network_[u][v];
  }

  ~Network() {
    for (size_t i = 0; i < getSize(); ++i) {
      for (auto it : inner_network_[i])
        delete it.second;
    }
  }
};

template <typename TScalar> class NetworkBuilder {
private:
  const vector<vector<pair<size_t, TScalar>>> &my_list_;
  size_t source_;
  size_t target_;

public:
  explicit NetworkBuilder(size_t source_, size_t target_,
                          const vector<vector<pair<size_t, TScalar>>> &my_list_)
      : source_(source_), target_(target_), my_list_(my_list_) {}

  INetwork<TScalar> *BuildNetwork() {
    auto m_network = new Network<TScalar>(source_, target_, my_list_.size());
    for (int i = 0; i < my_list_.size(); ++i) {
      for (auto it : my_list_[i]) {
        m_network->AddEdge(i, it.first, it.second);
      }
    }
    return m_network;
  }

  void setSource(size_t source_) { NetworkBuilder::source_ = source_; }

  void setTarget(size_t target_) { NetworkBuilder::target_ = target_; }
};

template <typename TScalar> class IFlowPerformer {
protected:
  INetwork<TScalar> *net_;

public:
  virtual TScalar PerformFlow() = 0;

  explicit IFlowPerformer(INetwork<TScalar> *m_network)
      : net_(std::move(m_network)) {}

  virtual ~IFlowPerformer() = default;
};

template <typename TScalar>
class PushFlowProfiler : public IFlowPerformer<TScalar> {
private:
  using IFlowPerformer<TScalar>::net_;
  static const size_t inf = numeric_limits<size_t>::max();
  size_t s_, t_;
  vector<size_t> heights;
  vector<TScalar> exceeds;
  vector<INetworkIterator<TScalar>> current_iterator;
  size_t exceeds_counter;

public:
  explicit PushFlowProfiler(INetwork<TScalar> *m_network)
      : IFlowPerformer<TScalar>(m_network), s_(net_->getSource()),
        t_(net_->getTarget()), heights(net_->getSize()),
        exceeds(net_->getSize()), exceeds_counter(0) {
    heights[s_] = net_->getSize();
  };

private:
  TScalar push(size_t u, size_t v) {
    TScalar flow =
        (u == s_) ? net_->GetEdge(u, v).capacity_ - net_->GetEdge(u, v).flow_
                  : std::min(exceeds[u], net_->GetEdge(u, v).capacity_ -
                                             net_->GetEdge(u, v).flow_);
    net_->AddFlow(u, v, flow);
    AlterExceed(u, -flow);
    AlterExceed(v, flow);
    return flow;
  }

  void AlterExceed(size_t u, TScalar flow) {
    auto pr = exceeds[u];
    exceeds[u] += flow;
    if (u != s_ && u != t_ && exceeds[u] == 0 && pr != 0)
      --exceeds_counter;
    else if (u != s_ && u != t_ && pr == 0 && exceeds[u] != 0)
      ++exceeds_counter;
  }

  void relabel(size_t u) {
    size_t minh = inf;
    auto it = net_->GetForwardIterator(u);
    while (it) {
      if (it->Flow() != it->Capacity())
        minh = std::min(minh, heights[it->To()]);
      ++it;
    }
    heights[u] = minh + 1;
  }

  void discharge(size_t u) {
    while (exceeds[u] > 0) {
      INetworkIterator<TScalar> it = current_iterator[u];
      if (!it) {
        relabel(u);
        current_iterator[u] = net_->GetForwardIterator(u);
      } else {
        if (it->Capacity() - it->Flow() > 0 &&
            heights[u] == heights[it->To()] + 1)
          push(u, it->To());
        else {
          ++current_iterator[u];
        }
      }
    }
  }

public:
  TScalar PerformFlow() override {
    for (size_t i = 0; i < net_->getSize(); ++i) {
      current_iterator.push_back(net_->GetForwardIterator(i));
    }
    for (auto it = net_->GetForwardIterator(s_); it; ++it) {
      push(s_, it->To());
    }
    while (exceeds_counter) {
      for (size_t i = 0; i < net_->getSize(); ++i) {
        if (i == s_ || i == t_)
          continue;
        discharge(i);
      }
    }
    TScalar ans = 0;
    for (auto it = net_->GetForwardIterator(s_); it; ++it) {
      ans += it->Flow();
    }
    return ans;
  }
};

int main() {
  size_t n, m;
  cin >> n >> m;
  vector<vector<pair<size_t, ll>>> m_list(n);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    m_list[u].push_back(std::make_pair(v, c));
  }
  auto m_network = NetworkBuilder<ll>(0, n - 1, m_list).BuildNetwork();
  auto m_profiler = PushFlowProfiler<ll>(m_network);
  cout << m_profiler.PerformFlow() << std::endl;
  delete m_network;
  return 0;
}



Measured memory_bytes: 3396