#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx")
using namespace std;
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2> p) {
  o << "(" << p.first << ":" << p.second << ")";
  return o;
}
mt19937 mt(8901016);
inline int rand_int(int l, int h) {
  return uniform_int_distribution<>(l, h)(mt);
}
namespace {
class MaiScanner {
 public:
  template <typename T>
  void input_integer(T& var) {
    var = 0;
    T sign = 1;
    int cc = getchar_unlocked();
    for (; cc < '0' || '9' < cc; cc = getchar_unlocked())
      if (cc == '-') sign = -1;
    for (; '0' <= cc && cc <= '9'; cc = getchar_unlocked())
      var = (var << 3) + (var << 1) + cc - '0';
    var = var * sign;
  }
  inline int c() { return getchar_unlocked(); }
  inline MaiScanner& operator>>(int& var) {
    input_integer<int>(var);
    return *this;
  }
  inline MaiScanner& operator>>(long long& var) {
    input_integer<long long>(var);
    return *this;
  }
  inline MaiScanner& operator>>(string& var) {
    int cc = getchar_unlocked();
    for (; !(0x21 <= (cc) && (cc) <= 0x7E); cc = getchar_unlocked())
      ;
    for (; (0x21 <= (cc) && (cc) <= 0x7E); cc = getchar_unlocked())
      var.push_back(cc);
  }
  template <typename IT>
  void in(IT begin, IT end) {
    for (auto it = begin; it != end; ++it) *this >> *it;
  }
};
}  // namespace
MaiScanner scanner;
class Flow {
 public:
  size_t n;
  struct Arrow {
    int from, to;
    int left;
    int cap;
    Arrow(int from = 0, int to = 0, int w = 1)
        : from(from), to(to), left(w), cap(w) {}
    bool operator<(const Arrow& a) const {
      return (from < a.from) | (to < a.to) | (left < a.left) | (cap < a.cap);
    }
    bool operator==(const Arrow& a) const {
      return (from == a.from) && (to == a.to) && (left == a.left) &&
             (cap == a.cap);
    }
  };
  vector<vector<int>> vertex_to;
  vector<vector<int>> vertex_from;
  vector<Arrow> arrow;
  Flow(int n, int m = 5010) : n(n), vertex_to(n), vertex_from(n) {
    arrow.reserve(m);
  }
  void connect(int from, int to, int left) {
    vertex_to[from].push_back(arrow.size());
    vertex_from[to].push_back(arrow.size());
    arrow.emplace_back(from, to, left);
  }
  size_t degree(int v) { return vertex_to[v].size() + vertex_from[v].size(); }
  size_t degree_in(int v) { return vertex_from[v].size(); }
  size_t degree_out(int v) { return vertex_to[v].size(); }
};
int _dinic_path_dfs(Flow& flow, vector<int>& result, vector<int>& flag,
                    const vector<int>& dist, int u, int i_sink, int mini) {
  if (i_sink == u) return mini;
  if (flag[u]) return -1;
  flag[u] = true;
  int sumw = 0;
  bool term = true;
  for (int e : flow.vertex_to[u]) {
    Flow::Arrow& a = flow.arrow[e];
    if (a.left > 0 && dist[u] > dist[a.to]) {
      int w;
      if (mini < 0)
        w = a.left;
      else
        w = min(a.left, mini);
      w = _dinic_path_dfs(flow, result, flag, dist, a.to, i_sink, w);
      if (w == -1) continue;
      a.left -= w;
      result[a.to] += w;
      sumw += w;
      mini -= w;
      term = false;
      flag[u] = false;
      if (mini == 0) return term ? -1 : sumw;
    }
  }
  for (int e : flow.vertex_from[u]) {
    Flow::Arrow& a = flow.arrow[e];
    if (a.cap > a.left && dist[u] > dist[a.from]) {
      int w;
      if (mini < 0)
        w = a.cap - a.left;
      else
        w = min(a.cap - a.left, mini);
      w = _dinic_path_dfs(flow, result, flag, dist, a.from, i_sink, w);
      if (w == -1) continue;
      a.left += w;
      result[a.to] -= w;
      sumw += w;
      mini -= w;
      term = false;
      flag[u] = false;
      if (mini == 0) return term ? -1 : sumw;
    }
  }
  return term ? -1 : sumw;
}
void dinic(Flow& flow, vector<int>& result, int i_source, int i_sink) {
  assert(i_source != i_sink);
  result.resize(flow.n);
  int distbegin = 0;
  vector<int> dist(flow.n);
  queue<int> q;
  vector<int> flag(flow.n);
  for (int distbegin = 0;; distbegin += flow.n) {
    q.emplace(i_sink);
    dist[i_sink] = distbegin + 1;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int ie : flow.vertex_from[v]) {
        const Flow::Arrow& e = flow.arrow[ie];
        if (0 < e.left && dist[e.from] <= distbegin) {
          dist[e.from] = dist[v] + 1;
          q.emplace(e.from);
        }
      }
      for (int ie : flow.vertex_to[v]) {
        const Flow::Arrow& e = flow.arrow[ie];
        if (e.left < e.cap && dist[e.to] <= distbegin) {
          dist[e.to] = dist[v] + 1;
          q.emplace(e.to);
        }
      }
    }
    fill((flag).begin(), (flag).end(), false);
    if (dist[i_source] <= distbegin) {
      break;
    } else {
      result[i_source] +=
          _dinic_path_dfs(flow, result, flag, dist, i_source, i_sink, -1);
    }
  }
}
long long int n, m;
int main() {
  scanner >> n >> m;
  Flow graph_orig(n);
  Flow graph(n);
  map<int, int> link;
  for (auto cnt = 0; cnt < (m); ++cnt) {
    int a, b, c;
    scanner >> a >> b >> c;
    --a;
    --b;
    int ia, ib;
    ia = graph.arrow.size();
    graph.connect(a, b, c);
    ib = graph.arrow.size();
    graph.connect(b, a, c);
    link[ia] = ib;
    link[ib] = ia;
    graph_orig.connect(a, b, c);
  }
  vector<int> result;
  dinic(graph, result, 0, n - 1);
  int fl = 0;
  int high = 0;
  for (int i = 0; i < graph.arrow.size(); ++i) {
    auto& a = graph.arrow[i];
    auto di = link[i];
    auto& d = graph.arrow[di];
    if (di < i) continue;
    if (a.left != a.cap && d.left != d.cap) {
      high = max(high, a.cap);
      fl += a.cap;
    }
  }
  cout << (fl - high) << endl;
  return 0;
}
