#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const int M = 5e4 + 10;
int n;
struct bian {
  int from, to;
  long long w, val;
} eg[M << 1];
int front[N], num;
void add(int x, int y, long long w, long long val) {
  eg[++num].to = y;
  eg[num].from = front[x];
  front[x] = num;
  eg[num].w = w;
  eg[num].val = val;
  eg[++num].to = x;
  eg[num].from = front[y];
  front[y] = num;
  eg[num].val = -val;
}
long long dis[N], in[N], out[N];
int _front[N];
int s, t, S, T;
int vis[N];
bool bfs() {
  queue<int> q;
  q.push(s);
  for (int i = 1; i <= t; ++i) {
    dis[i] = 1e18;
  }
  dis[s] = 0;
  while (!q.empty()) {
    int o = q.front();
    q.pop();
    vis[o] = 0;
    for (int i = front[o]; i; i = eg[i].from) {
      int to = eg[i].to;
      if (eg[i].w && dis[to] > dis[o] + eg[i].val) {
        dis[to] = dis[o] + eg[i].val;
        if (vis[to] == 0) {
          vis[to] = 1;
          q.push(to);
        }
      }
    }
  }
  return dis[t] != 1e18;
}
long long cost;
long long dfs(int o, long long lim) {
  if (o == t) return lim;
  vis[o] = 1;
  long long mins = 0;
  for (int &i = _front[o]; i; i = eg[i].from) {
    int to = eg[i].to;
    if (vis[to] == 1 || dis[to] != dis[o] + eg[i].val || eg[i].w == 0) continue;
    long long now = dfs(to, min(lim - mins, eg[i].w));
    if (now) {
      cost += now * eg[i].val;
      eg[i].w -= now;
      eg[((i - 1) ^ 1) + 1].w += now;
      mins += now;
      if (mins == lim) break;
    }
  }
  vis[o] = 0;
  return mins;
}
long long dinic() {
  long long re = 0;
  while (bfs()) {
    memcpy(_front, front, sizeof(front));
    long long gu;
    while (gu = dfs(s, 1e18)) {
      re += gu;
    }
  }
  return re;
}
int m;
int main() {
  scanf("%d%d", &n, &m);
  S = 1;
  T = n;
  s = T + 1;
  t = s + 1;
  for (int i = 1; i <= m; ++i) {
    int x, y, f, c;
    scanf("%d%d%d%d", &x, &y, &c, &f);
    in[y] += f;
    out[x] += f;
    if (c >= f)
      add(y, x, f, 1), add(x, y, c - f, 1), add(x, y, 1e9, 2);
    else
      add(y, x, f - c, 0), add(y, x, c, 1), add(x, y, 1e9, 2), cost += f - c;
  }
  int zong = 0;
  for (int i = 1; i <= T; ++i) {
    if (in[i] > out[i])
      add(s, i, in[i] - out[i], 0), zong += in[i] - out[i];
    else
      add(i, t, out[i] - in[i], 0);
  }
  add(T, S, 1e9, 0);
  dinic();
  printf("%d", cost);
}
