#include <bits/stdc++.h>
using namespace std;
template <typename tp>
inline void read(tp &x) {
  x = 0;
  char c = getchar();
  int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
  if (f) x = -x;
}
namespace mf {
const long long N = 1e3 + 233;
const long long M = 2e5 + 233;
const long long MAXFLOW = 1e15;
const long long MAXCOST = 1e15;
struct E {
  long long nxt, to;
  long long fl, w;
} e[M];
long long head[N], e_cnt = 1, cur[N];
long long d[N];
bool book[N];
long long all;
inline void init(long long n) {
  all = n;
  for (register long long i = 0; i < (long long)all + 1; i++) head[i] = 0;
  e_cnt = 1;
}
inline void adde(long long x, long long y, long long fl, long long w) {
  e[++e_cnt] = (E){head[x], y, fl, w};
  head[x] = e_cnt;
}
inline void link(long long x, long long y, long long fl, long long w) {
  adde(x, y, fl, w);
  adde(y, x, 0, -w);
}
inline bool spfa(long long S, long long T) {
  for (register long long i = 0; i < (long long)all + 1; i++)
    d[i] = MAXCOST, book[i] = 0;
  queue<long long> Q;
  book[S] = true;
  d[S] = 0;
  Q.push(S);
  while (!Q.empty()) {
    long long u = Q.front();
    Q.pop();
    book[u] = false;
    for (long long i = head[u]; i; i = e[i].nxt)
      if (e[i ^ 1].fl) {
        long long v = e[i].to;
        if (d[v] > d[u] + e[i ^ 1].w) {
          d[v] = d[u] + e[i ^ 1].w;
          if (!book[v]) Q.push(v), book[v] = true;
        }
      }
  }
  return d[T] != MAXCOST;
}
inline long long dfs(long long u, long long f, long long T) {
  book[u] = true;
  if (u == T || !f) return f;
  long long used = 0, t;
  for (long long &i = cur[u]; i; i = e[i].nxt)
    if (e[i].fl) {
      long long v = e[i].to;
      if (book[v] || d[u] != d[v] + e[i].w) continue;
      t = dfs(v, min(f - used, e[i].fl), T);
      e[i].fl -= t;
      e[i ^ 1].fl += t;
      used += t;
      if (used == f) break;
    }
  if (used == 0) d[u] = MAXCOST;
  return used;
}
pair<long long, long long> doit(long long S, long long T) {
  long long maxflow = 0;
  long long mincost = 0;
  while (spfa(T, S)) {
    for (register long long i = 0; i < (long long)all + 1; i++)
      cur[i] = head[i], book[i] = 0;
    long long t = dfs(S, MAXFLOW, T);
    maxflow += t;
    mincost += t * d[S];
  }
  return make_pair(maxflow, mincost);
}
}  // namespace mf
using mf::link;
const long long N = 444;
long long n, m, ans;
long long in[N], out[N];
signed main(void) {
  read(n);
  read(m);
  long long ss = n, tt = ss + 1;
  mf::init(tt);
  for (register long long i = 1; i <= (m); i++) {
    long long x, y, cap, f;
    read(x);
    read(y);
    read(cap);
    read(f);
    if (y == n) y = 1;
    in[y] += f;
    out[x] += f;
    if (f <= cap) {
      link(y, x, f, 1);
      link(x, y, cap - f, 1);
      link(x, y, mf::MAXFLOW, 2);
    } else {
      ans += f - cap;
      link(y, x, f - cap, 0);
      link(y, x, cap, 1);
      link(x, y, mf::MAXFLOW, 2);
    }
  }
  for (register long long y = 1; y <= (n - 1); y++) {
    long long t = abs(out[y] - in[y]);
    if (in[y] > out[y])
      link(ss, y, t, 0);
    else
      link(y, tt, t, 0);
  }
  auto it = mf::doit(ss, tt);
  cout << ans + it.second << "\n";
}
