#include <bits/stdc++.h>
using namespace std;
const int inf = 1e8;
const int N = 105;
int n, m, s, t, tot = 1, ans;
int head[N], nxt[N << 4], to[N << 4], w[N << 4], val[N << 4], deg[N];
inline void link(int a, int b, int c, int d) {
  nxt[++tot] = head[a];
  to[head[a] = tot] = b;
  w[tot] = c;
  val[tot] = d;
  nxt[++tot] = head[b];
  to[head[b] = tot] = a;
  w[tot] = 0;
  val[tot] = -d;
}
inline bool spfa(int s, int t, bool opt) {
  static bool inq[N];
  static int dis[N], pre[N], f[N];
  queue<int> q;
  memset(pre, 0, sizeof(pre));
  memset(f, 0, sizeof(f));
  memset(dis, 0x3f, sizeof(dis));
  q.push(s);
  dis[s] = 0;
  f[s] = inf;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    inq[x] = 0;
    for (int i = head[x]; i; i = nxt[i])
      if (w[i] && dis[x] + val[i] < dis[to[i]]) {
        dis[to[i]] = dis[x] + val[i];
        pre[to[i]] = i;
        f[to[i]] = min(f[x], w[i]);
        if (!inq[to[i]]) inq[to[i]] = 1, q.push(to[i]);
      }
  }
  if ((!opt && dis[t] > inf) || (opt && dis[t] >= 0)) return 0;
  int flow = f[t];
  ans += flow * dis[t];
  for (int x = t; x ^ s; x = to[pre[x] ^ 1])
    w[pre[x]] -= flow, w[pre[x] ^ 1] += flow;
  return 1;
}
int main() {
  scanf("%d%d", &n, &m);
  s = n + 1;
  t = s + 1;
  for (int i = 1, x, y, c, f; i <= m; ++i) {
    scanf("%d%d%d%d", &x, &y, &c, &f);
    deg[x] += f;
    deg[y] -= f;
    if (f <= c) {
      link(x, y, c - f, 1);
      link(x, y, inf, 2);
      link(y, x, f, 1);
    } else {
      ans += f - c;
      link(x, y, inf, 2);
      link(y, x, f - c, 0);
      link(y, x, c, 1);
    }
  }
  int lst = tot;
  for (int i = 1; i <= n; ++i)
    if (deg[i] > 0)
      link(i, t, deg[i], 0);
    else if (deg[i] < 0)
      link(s, i, -deg[i], 0);
  link(n, 1, inf, 0);
  while (spfa(s, t, 0))
    ;
  for (int i = lst; i <= tot; ++i) w[i] = 0;
  while (spfa(1, n, 1))
    ;
  printf("%d\n", ans);
  return 0;
}
