#include <bits/stdc++.h>
using namespace std;
int S = 0, T = 101;
struct edge {
  int s, t, cap, v, nxt;
} e[2005];
int e_cnt, last[105];
void ins(int a, int b, int c, int d) {
  e[e_cnt] = (edge){a, b, c, d, last[a]};
  last[a] = e_cnt++;
}
int d[105], c[105], fa[105];
bool vis[105];
bool dij() {
  memset(d, 63, sizeof(d));
  memset(c, 0, sizeof(c));
  memset(vis, 0, sizeof(vis));
  d[S] = 0;
  c[S] = 1e9;
  for (int i = 0; i <= T; i++) {
    int x = -1;
    for (int j = 0; j <= T; j++)
      if (!vis[j] && (x == -1 || d[j] < d[x])) x = j;
    if (x == -1 || !c[x]) break;
    vis[x] = 1;
    for (int i = last[x]; i != -1; i = e[i].nxt)
      if (!vis[e[i].t] && e[i].cap && d[e[i].t] > d[x] + e[i].v) {
        d[e[i].t] = d[x] + e[i].v;
        c[e[i].t] = min(c[x], e[i].cap);
        fa[e[i].t] = i;
      }
  }
  return c[T] > 0;
}
pair<int, int> solve() {
  int flow = 0, cost = 0, r = 0;
  while (dij()) {
    int F = c[T];
    flow += F;
    int u = T;
    while (u != S) {
      e[fa[u]].cap -= F;
      e[fa[u] ^ 1].cap += F;
      u = e[fa[u]].s;
    }
    r += d[T];
    cost += r * F;
    for (int i = 0; i < e_cnt; i++) e[i].v = d[e[i].s] + e[i].v - d[e[i].t];
  }
  return make_pair(flow, cost);
}
inline void add(int a, int b, int c, int d) {
  ins(a, b, c, d);
  ins(b, a, 0, -d);
}
int h[105];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int ans = 0;
  memset(last, -1, sizeof(last));
  for (int i = 1; i <= m; i++) {
    int u, v, c, f;
    scanf("%d%d%d%d", &u, &v, &c, &f);
    h[u] -= f;
    h[v] += f;
    if (f > c) {
      ans += f - c;
      add(v, u, f - c, 0);
      add(v, u, c, 1);
      add(u, v, 1e9, 2);
    } else {
      add(v, u, f, 1);
      add(u, v, c - f, 1);
      add(u, v, 1e9, 2);
    }
  }
  add(n, 1, 1e9, 0);
  for (int i = 1; i <= n; i++)
    if (h[i] < 0)
      add(i, T, -h[i], 0);
    else if (h[i] > 0)
      add(S, i, h[i], 0);
  printf("%d\n", ans + solve().second);
}
