#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const long long N = 5000;
long long n, m, s, t;
vector<pair<long long, pair<long long, long long> > > nei[N + 1];
vector<long long> rv[N + 1];
void ae(long long x, long long y, long long c, long long w) {
  nei[x].push_back(make_pair(y, make_pair(c, w))),
      nei[y].push_back(make_pair(x, make_pair(0, -w)));
  rv[x].push_back(nei[y].size() - 1), rv[y].push_back(nei[x].size() - 1);
}
long long sumf[N + 1];
long long noww;
void rl_ae(long long x, long long y, long long l, long long r, long long w) {
  ae(x, y, r - l, w);
  sumf[x] += l, sumf[y] -= l;
  noww += l * w;
}
long long dis[N + 1], prv[N + 1];
bool inq[N + 1];
bool spfa() {
  memset(dis, 0x3f, sizeof(dis));
  memset(inq, 0, sizeof(inq));
  dis[s] = 0;
  queue<long long> q;
  q.push(s), inq[s] = true;
  while (q.size()) {
    long long x = q.front();
    q.pop(), inq[x] = false;
    for (long long i = 0; i < nei[x].size(); i++) {
      long long y = nei[x][i].first, &c = nei[x][i].second.first,
                w = nei[x][i].second.second;
      if (c && dis[x] + w < dis[y]) {
        dis[y] = dis[x] + w, prv[y] = rv[x][i];
        if (!inq[y]) q.push(y), inq[y] = true;
      }
    }
  }
  return dis[t] < inf;
}
pair<long long, long long> ek() {
  long long resf = 0, resw = 0;
  while (spfa()) {
    long long flw = inf;
    for (long long i = t; i != s; i = nei[i][prv[i]].first)
      flw = min(flw, nei[nei[i][prv[i]].first][rv[i][prv[i]]].second.first);
    for (long long i = t; i != s; i = nei[i][prv[i]].first)
      nei[nei[i][prv[i]].first][rv[i][prv[i]]].second.first -= flw,
          nei[i][prv[i]].second.first += flw;
    resf += flw, resw += dis[t] * flw;
  }
  return make_pair(resf, resw);
}
signed main() {
  cin >> n >> m;
  s = 1, t = n;
  while (m--) {
    long long x, y, c, f;
    cin >> x >> y >> c >> f;
    rl_ae(x, y, f, f, 0);
    if (f <= c) {
      rl_ae(x, y, 0, c - f, 1);
      rl_ae(x, y, 0, inf, 2);
      rl_ae(y, x, 0, f, 1);
    } else {
      noww += f - c;
      rl_ae(y, x, 0, f - c, 0);
      rl_ae(y, x, 0, c, 1);
      rl_ae(x, y, 0, inf, 2);
    }
  }
  rl_ae(t, s, 0, inf, 0);
  s = n + 1, t = n + 2;
  for (long long i = 1; i < s; i++)
    if (sumf[i] < 0)
      ae(s, i, -sumf[i], 0);
    else
      ae(i, t, sumf[i], 0);
  pair<long long, long long> ans = ek();
  cout << noww + ans.second << "\n";
  return 0;
}
