#include <bits/stdc++.h>
using namespace std;
struct edge {
  long long to, cap, cost, rev;
};
long long dist[105], h[105], prevv[105], preve[105];
long long V, n, m;
vector<edge> G[105];
void add_edge(long long from, long long to, long long cap, long long cost) {
  G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
  G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1});
}
long long min_cost_flow(long long s, long long t, long long f) {
  long long res = 0;
  fill(h + 1, h + V + 1, 0);
  while (f > 0) {
    priority_queue<pair<long long, long long>,
                   vector<pair<long long, long long> >,
                   greater<pair<long long, long long> > >
        que;
    fill(dist + 1, dist + V + 1, 1000000000);
    dist[s] = 0;
    que.push(pair<long long, long long>(0, s));
    while (!que.empty()) {
      pair<long long, long long> p = que.top();
      que.pop();
      long long v = p.second;
      if (dist[v] < p.first) continue;
      for (long long i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
          dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
          prevv[e.to] = v;
          preve[e.to] = i;
          que.push(pair<long long, long long>(dist[e.to], e.to));
        }
      }
    }
    if (dist[t] == 1000000000) {
      return -1;
    }
    for (long long v = 1; v <= V; v++) h[v] += dist[v];
    long long d = f;
    for (long long v = t; v != s; v = prevv[v]) {
      d = min(d, G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d * h[t];
    for (long long v = t; v != s; v = prevv[v]) {
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}
long long cnt[105];
int main() {
  scanf("%lld%lld", &n, &m);
  V = n + 2;
  long long s = n + 1, t = n + 2, ans = 0;
  for (long long i = 0; i < m; i++) {
    long long u, v, c, f;
    scanf("%lld%lld%lld%lld", &u, &v, &c, &f);
    cnt[u] -= f;
    cnt[v] += f;
    if (f <= c) {
      add_edge(u, v, c - f, 1);
      add_edge(u, v, 1000000000, 2);
      add_edge(v, u, f, 1);
    } else {
      ans += f - c;
      add_edge(u, v, 1000000000, 2);
      add_edge(v, u, f - c, 0);
      add_edge(v, u, c, 1);
    }
  }
  add_edge(1, n, 1000000000, 0);
  add_edge(n, 1, 1000000000, 0);
  long long sum = 0;
  for (long long i = 1; i <= n; i++) {
    if (cnt[i] > 0) {
      add_edge(s, i, cnt[i], 0);
      sum += cnt[i];
    } else
      add_edge(i, t, -cnt[i], 0);
  }
  ans += min_cost_flow(s, t, sum);
  printf("%lld\n", ans);
  return 0;
}
