#include <bits/stdc++.h>
using namespace std;
const int maxn = 105, maxm = 2005;
struct edge {
  int to, next, w, cost;
} lst[maxm];
int len = 0, first[maxn];
void addedge(int a, int b, int w, int cost) {
  lst[len].to = b;
  lst[len].next = first[a];
  lst[len].w = w;
  lst[len].cost = cost;
  first[a] = len++;
  lst[len].to = a;
  lst[len].next = first[b];
  lst[len].w = 0;
  lst[len].cost = -cost;
  first[b] = len++;
}
bool inq[maxn];
int q[maxn], vis[maxn], dis[maxn], prt[maxn], flow[maxn], head, tail, T, s, t;
bool spfa() {
  head = tail = 0;
  vis[s] = ++T;
  dis[s] = 0;
  prt[s] = -1;
  flow[s] = 0x7f7f7f7f;
  q[tail++] = s;
  inq[s] = true;
  while (head != tail) {
    int x = q[head++];
    inq[x] = false;
    head %= maxn;
    for (int pt = first[x]; pt != -1; pt = lst[pt].next) {
      if (lst[pt].w == 0) continue;
      if (vis[lst[pt].to] != T || dis[lst[pt].to] > dis[x] + lst[pt].cost) {
        vis[lst[pt].to] = T;
        dis[lst[pt].to] = dis[x] + lst[pt].cost;
        prt[lst[pt].to] = pt;
        flow[lst[pt].to] = min(lst[pt].w, flow[x]);
        if (!inq[lst[pt].to]) {
          q[tail++] = lst[pt].to;
          tail %= maxn;
          inq[lst[pt].to] = true;
        }
      }
    }
  }
  return vis[t] == T;
}
long long mincost() {
  long long cost = 0;
  while (spfa() && dis[t] < 0) {
    cost += flow[t] * 1LL * dis[t];
    for (int pt = prt[t]; pt != -1; pt = prt[lst[pt ^ 1].to]) {
      lst[pt].w -= flow[t];
      lst[pt ^ 1].w += flow[t];
    }
  }
  return cost;
}
int n, m;
long long sum = 0;
int totflow[maxn], u[maxn], v[maxn], c[maxn], f[maxn];
void build_graph() {
  memset(first, -1, sizeof(first));
  s = 0;
  t = n + 1;
  for (int i = 2; i < n; ++i) {
    if (totflow[i] > 0) {
      addedge(s, i, totflow[i], -1000);
      sum += 1000LL * totflow[i];
    } else if (totflow[i] < 0) {
      addedge(i, t, -totflow[i], -1000);
      sum += 1000LL * -(totflow[i]);
    }
  }
  addedge(s, 1, 0x7f7f7f7f, 0);
  addedge(s, n, 0x7f7f7f7f, 0);
  addedge(1, t, 0x7f7f7f7f, 0);
  addedge(n, t, 0x7f7f7f7f, 0);
  for (int i = 1; i <= m; ++i) {
    if (f[i] < c[i]) {
      addedge(u[i], v[i], c[i] - f[i], 1);
      addedge(u[i], v[i], 0x7f7f7f7f, 2);
      addedge(v[i], u[i], f[i], 1);
    } else {
      sum += f[i] - c[i];
      addedge(v[i], u[i], f[i] - c[i], 0);
      addedge(v[i], u[i], c[i], 1);
      addedge(u[i], v[i], 0x7f7f7f7f, 2);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d%d", u + i, v + i, c + i, f + i);
    totflow[u[i]] -= f[i];
    totflow[v[i]] += f[i];
  }
  build_graph();
  printf("%lld\n", mincost() + sum);
  return 0;
}
