#include <algorithm>
#include <iostream>
#include <memory>
#include <queue>
#include <unordered_map>
#include <iterator>
#include <cassert>

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;
using std::make_pair;
using std::queue;

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 = nullptr)
      : impl(std::move(r)) {}

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

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

  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;

  virtual INetwork *clone() const = 0;

  virtual INetwork *create(size_t source_, size_t target_, size_t size_) const = 0;
};

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:
  INetwork<TScalar> *create(size_t source_, size_t target_, size_t size_) const override {
    return new Network<TScalar>(source_, target_, size_);
  }

  INetwork<TScalar> *clone() const override {
    return new Network(*this);
  }

  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_;

  virtual void init(INetwork<TScalar> *net_) = 0;

 public:
  virtual TScalar PerformFlow() = 0;

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

  virtual ~IFlowPerformer() {
    delete net_;
  };

  void setNet(INetwork<TScalar> *net_) {
    init(net_);
  }

};

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

 public:

  explicit PushFlowPerformer(INetwork<TScalar> *m_network)
      : IFlowPerformer<TScalar>(m_network) {
    init(m_network);
  };

 private:
  void init(INetwork<TScalar> *m_network) override {
    net_ = m_network;
    if (net_!=nullptr) {
      source_ = net_->getSource();
      target_ = net_->getTarget();
      heights = vector<size_t>(net_->getSize());
      exceeds = vector<TScalar>(net_->getSize());
      exceeds_counter = 0;
      heights[source_] = net_->getSize();
    }
  }

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

  void AlterExceed(size_t u, TScalar flow) {
    auto pr = exceeds[u];
    exceeds[u] += flow;
    if (u!=source_ && u!=target_ && exceeds[u]==0 && pr!=0)
      --exceeds_counter;
    else if (u!=source_ && u!=target_ && 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(source_); it; ++it) {
      push(source_, it->To());
    }
    while (exceeds_counter) {
      for (size_t i = 0; i < net_->getSize(); ++i) {
        if (i==source_ || i==target_)
          continue;
        discharge(i);
      }
    }
    TScalar ans = 0;
    for (auto it = net_->GetForwardIterator(source_); it; ++it) {
      ans += it->Flow();
    }
    return ans;
  }
};

template<typename TScalar>
class MalhotraFlowPerformer : public IFlowPerformer<TScalar> {
 public:
  explicit MalhotraFlowPerformer(INetwork<TScalar> *m_network)
      : IFlowPerformer<TScalar>(m_network) {
    init(m_network);
  };
 private:
  INetwork<TScalar> *layered_network_;
  using IFlowPerformer<TScalar>::net_;
  vector<TScalar> potentials_in_;
  vector<TScalar> potentials_out_;
  vector<size_t> to_delete_;
  vector<bool> working_vertices_;
  vector<INetworkIterator<TScalar>> current_iterator_front_;
  vector<INetworkIterator<TScalar>> current_iterator_back_;

  void init(INetwork<TScalar> *net_) override {
    this->net_ = net_;
    if (net_!=nullptr) {
      size_t sz = net_->getSize();
      potentials_in_ = vector<TScalar>(sz);
      potentials_out_ = vector<TScalar>(sz);
      working_vertices_ = vector<bool>(sz, true);
      current_iterator_front_ = vector<INetworkIterator<TScalar>>(sz);
      current_iterator_back_ = vector<INetworkIterator<TScalar>>(sz);
    }
  }

  TScalar GetPotential(size_t vertex) {
    if (vertex==layered_network_->getSource())
      return potentials_out_[vertex];
    else if (vertex==layered_network_->getTarget())
      return potentials_in_[vertex];
    return std::min(potentials_out_[vertex], potentials_in_[vertex]);
  }

  void DeleteVertex(size_t vertex);

  void UpdatePotential(size_t vertex) {
    if (!working_vertices_[vertex])
      return;
    potentials_in_[vertex] = potentials_out_[vertex] = 0;
    for (auto it = layered_network_->GetForwardIterator(vertex); it; ++it) {
      if (it->Capacity()==0)
        continue;
      if (working_vertices_[it->To()])
        potentials_out_[vertex] += it->Capacity() - it->Flow();
    }
    for (auto it = layered_network_->GetBackIterator(vertex); it; ++it) {
      if (it->Capacity()==0)
        continue;
      if (working_vertices_[it->From()])
        potentials_in_[vertex] += it->Capacity() - it->Flow();

    }
    if (GetPotential(vertex)==0)
      DeleteVertex(vertex);
  }

  bool BuildLayeredNetwork() {
    layered_network_ = net_->create(net_->getSource(), net_->getTarget(), net_->getSize());
    const size_t inf = std::numeric_limits<size_t>::max();
    vector<size_t> dist_(net_->getSize(), inf);
    std::queue<size_t> mq;
    dist_[net_->getSource()] = 0;
    mq.push(net_->getSource());
    while (!mq.empty()) {
      size_t x = mq.front();
      mq.pop();
      for (auto it = net_->GetForwardIterator(x); it; ++it) {
        if (it->Capacity() == 0)
          continue;
        if (it->Capacity() - it->Flow() > 0) {
          if (dist_[it->To()]==inf) {
            dist_[it->To()] = dist_[x] + 1;
            mq.push(it->To());
          }
          if (dist_[it->To()]==dist_[x] + 1) {
            layered_network_->AddEdge(x, it->To(), it->Capacity());
            layered_network_->AddFlow(x, it->To(), it->Flow());
          }
        }
      }
    }
    vector<bool> color(net_->getSize());
    delete_unwanted(net_->getTarget(), color);
    for (size_t i = 0; i < layered_network_->getSize(); ++i) {
      if (dist_[i]==inf || !color[i]) {
        working_vertices_[i] = false;
        continue;
      }
      working_vertices_[i] = true;
      current_iterator_front_[i] = layered_network_->GetForwardIterator(i);
      current_iterator_back_[i] = layered_network_->GetBackIterator(i);
    }
    bool ans = dist_[net_->getTarget()]!=inf;
    if (!ans)
      delete layered_network_;
    return ans;
  }

  void delete_unwanted(size_t vertex, vector<bool> &color) {
    color[vertex] = true;
    for (auto it = layered_network_->GetBackIterator(vertex); it; ++it) {
      if (it->Capacity()==0)
        continue;
      if (!color[it->From()])
        delete_unwanted(it->From(), color);
    }
  }

  void PushFlow(size_t start, TScalar flow, bool direction = true) {
    queue<pair<size_t, TScalar>> m_queue;
    m_queue.push(make_pair(start, flow));
    auto &current_container = (direction) ? current_iterator_front_ : current_iterator_back_;
    while (!m_queue.empty()) {
      size_t u = m_queue.front().first;
      flow = m_queue.front().second;
      m_queue.pop();
      while (flow) {
        auto it = current_container[u];
        assert(it);
        if (it->Capacity()==0) {
          ++current_container[u];
          continue;
        }
        size_t to = (it->To()==u) ? it->From() : it->To();
        if (working_vertices_[to]) {
          TScalar new_flow = std::min(it->Capacity() - it->Flow(), flow);
          if (new_flow==0) {
            ++current_container[u];
            continue;
          }
          if (new_flow!=flow)
            ++current_container[u];
          if (!direction)
            std::swap(u, to);
          layered_network_->AddFlow(u, to, new_flow);
          potentials_out_[u] -= new_flow;
          potentials_in_[to] -= new_flow;
          if (GetPotential(u)==0)
            to_delete_.push_back(u);
          if (GetPotential(to)==0)
            to_delete_.push_back(to);
          net_->AddFlow(u, to, new_flow);
          flow -= new_flow;
          if (!direction)
            std::swap(u, to);
          if (to!=layered_network_->getSource() && to!=layered_network_->getTarget())
            m_queue.push(make_pair(to, new_flow));
        }
        else
          ++current_container[u];
      }
    }
  }

  size_t CountPotentials() {
    TScalar mp = std::numeric_limits<TScalar>::max();
    size_t min_pot = mp;
    for (size_t i = 0; i < net_->getSize(); ++i) {
      if (!working_vertices_[i])
        continue;
      UpdatePotential(i);
      TScalar pot = GetPotential(i);
      if (pot && mp > pot) {
        mp = pot;
        min_pot = i;
      }
    }
    return min_pot;
  }

 public:
  TScalar PerformFlow() override {
    TScalar maxflow = 0;
    while (BuildLayeredNetwork()) {
      static size_t reference_vertex;
      while ((reference_vertex = CountPotentials()) < net_->getSize()) {
        TScalar cur_potential = GetPotential(reference_vertex);
        maxflow += cur_potential;
        if (reference_vertex!=net_->getTarget())
          PushFlow(reference_vertex, cur_potential, true);
        if (reference_vertex!=net_->getSource())
          PushFlow(reference_vertex, cur_potential, false);
        for (auto del : to_delete_)
          DeleteVertex(del);
        to_delete_.clear();
      }
      delete layered_network_;
    }
    return maxflow;
  }
};

template<typename TScalar>
void MalhotraFlowPerformer<TScalar>::DeleteVertex(size_t vertex) {
  if (!working_vertices_[vertex])
    return;
  working_vertices_[vertex] = false;
  for (auto it = layered_network_->GetForwardIterator(vertex); it; ++it) {
    if (it->Capacity()==0 || !working_vertices_[it->To()])
      continue;
    potentials_in_[it->To()] -= it->Capacity() - it->Flow();
    if (GetPotential(it->To())==0)
      DeleteVertex(it->To());
  }
  for (auto it = layered_network_->GetBackIterator(vertex); it; ++it) {
    if (it->Capacity()==0 || !working_vertices_[it->From()])
      continue;
    potentials_out_[it->From()] -= it->Capacity() - it->Flow();
    if (GetPotential(it->From())==0)
      DeleteVertex(it->From());
  }
}

class Controller {
 public:
  using TScalar = long long;
 private:
  TScalar pos_sum;
  TScalar answer;
  IFlowPerformer<TScalar> &m_performer;
  static const TScalar inf;

  template<typename InputIterator>
  static typename std::iterator_traits<InputIterator>::value_type
  ReadInput(InputIterator &iter) {
    TScalar ans = *iter;
    ++iter;
    return ans;
  }

 public:
  explicit Controller(IFlowPerformer<TScalar> &m_performer);

  template<typename InputIterator>
  void ReadData(InputIterator iter) {
    size_t n = ReadInput(iter);
    vector<vector<pair<size_t, TScalar >>> m_list(n + 2);
    for (size_t i = 0; i < n; ++i) {
      static TScalar cost;
      cost = ReadInput(iter);
      if (cost < 0) {
        m_list[i].push_back(std::make_pair(n + 1, -cost));
      } else {
        m_list[n].push_back(make_pair(i, cost));
        pos_sum += cost;
      }
    }
    for (size_t i = 0; i < n; ++i) {
      static size_t c;
      c = ReadInput(iter);
      for (size_t j = 0; j < c; ++j) {
        static size_t to;
        to = ReadInput(iter);
        --to;
        m_list[i].push_back(make_pair(to, inf));
      }
    }
    m_performer.setNet(NetworkBuilder<TScalar>(n, n + 1, m_list).BuildNetwork());
  }

  void ProceedData() {
    answer = pos_sum - m_performer.PerformFlow();
  }

  template<typename OutputIterator>
  void PrintData(OutputIterator iter) {
    *iter = answer;
  }

};

const Controller::TScalar  Controller::inf = 1000000000000ll;

Controller::Controller(IFlowPerformer<Controller::TScalar> &m_performer)
    : m_performer(m_performer), answer(0), pos_sum(0) {}

typedef long long ll;

int main() {
  size_t n, m;
  cin >> n >> m;
  vector<vector<pair<size_t, long long>>> 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_profiler = PushFlowPerformer<ll>(NetworkBuilder<ll>(0, n - 1, m_list).BuildNetwork());
  cout << m_profiler.PerformFlow() << std::endl;
  /*freopen("in.txt", "r", stdin);
  MalhotraFlowPerformer<Controller::TScalar> m_profiler(nullptr);
  Controller m_controller(m_profiler);
  m_controller.ReadData(std::istream_iterator<Controller::TScalar>(cin));
  m_controller.ProceedData();
  m_controller.PrintData(std::ostream_iterator<Controller::TScalar>(cout));*/
  return 0;
}



Measured memory_bytes: 3388