#include <bits/stdc++.h>
using namespace std;
const long long INF = 1E12;
struct edge {
  int f, t;
  long long cap, fl, pr;
  edge(int _f = 0, int _t = 0, long long _cap = 0, long long _pr = 0) {
    f = _f, t = _t, cap = _cap, pr = _pr, fl = 0;
  }
};
int N, F, T;
vector<edge> E;
vector<int> fo[110];
void add_edge(int f, int t, long long cap, long long pr) {
  E.push_back(edge(f, t, cap, pr)), fo[f].push_back(((int)(E).size()) - 1);
  E.push_back(edge(t, f, 0, -pr)), fo[t].push_back(((int)(E).size()) - 1);
}
long long sp[110];
int par[110];
deque<int> use;
bool used[110];
bool spfa() {
  memset(used, 0, N * sizeof(bool));
  for (int i = 0; i < N; ++i) sp[i] = INF;
  use.clear();
  use.push_back(F), sp[F] = 0;
  while (!use.empty()) {
    int vr = use[0];
    use.pop_front();
    used[vr] = false;
    for (int i = 0; i < ((int)(fo[vr]).size()); ++i) {
      edge& e = E[fo[vr][i]];
      if (e.cap > e.fl)
        if (sp[e.t] > sp[e.f] + e.pr) {
          par[e.t] = fo[vr][i];
          sp[e.t] = sp[e.f] + e.pr;
          if (!used[e.t]) used[e.t] = true, use.push_back(e.t);
        }
    }
  }
  return sp[T] < INF;
}
long long mfmc() {
  long long COST = 0;
  while (spfa()) {
    long long how = INF;
    int Last = T;
    while (Last != F) {
      (how) = min((how), (E[par[Last]].cap - E[par[Last]].fl));
      Last = E[par[Last]].f;
    }
    Last = T;
    while (Last != F) {
      COST += E[par[Last]].pr * how;
      E[par[Last]].fl += how;
      E[par[Last] ^ 1].fl -= how;
      Last = E[par[Last]].f;
    }
  }
  return COST;
}
int n, m;
int OF, OT;
long long base = 0;
long long bal[110];
void AddEdge(int f, int t, long long c, long long flow) {
  if (c >= flow) {
    add_edge(t, f, flow, 1);
    add_edge(f, t, INF, 2);
    add_edge(f, t, c - flow, 1);
  } else {
    base += abs(c - flow);
    add_edge(t, f, abs(c - flow), 0);
    add_edge(t, f, flow - abs(c - flow), 1);
    add_edge(f, t, INF, 2);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  N = n + 4;
  F = N - 4, T = N - 3;
  OF = N - 2, OT = N - 1;
  for (int i = 0; i < m; ++i) {
    int f, t, c, flow;
    scanf("%d%d%d%d", &f, &t, &c, &flow);
    --f, --t;
    AddEdge(f, t, c, flow);
    bal[t] += flow, bal[f] -= flow;
  }
  add_edge(n - 1, 0, INF, 0);
  for (int i = 0; i < n; ++i) {
    if (bal[i] > 0) {
      add_edge(F, i, abs(bal[i]), 0);
    } else if (bal[i] < 0) {
      add_edge(i, T, abs(bal[i]), 0);
    }
  }
  long long ans = mfmc() + base;
  cout << ans << '\n';
  return 0;
}
