#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const long long OO = 0x3f3f3f3f3f3f3f3fLL;
const int oo = 0x3f3f3f3f;
const int max0 = 10000, max1 = 100000;
struct edge {
  int id, g, w, nxt;
  edge() {}
  edge(const int &_id, const int &_g, const int &_w, const int &_nxt)
      : id(_id), g(_g), w(_w), nxt(_nxt) {}
};
int st[max0 + 5], en = 0;
edge e[max1 + 5];
int N;
inline void add_edge(const int &first, const int &second, const int &z,
                     const int &w) {
  e[en] = edge(second, z, w, st[first]), st[first] = en++;
}
inline void add_biedge(int first, int second, int z, const int &w) {
  if (!z) return;
  if (z < 0) swap(first, second), z = -z;
  add_edge(first, second, z, w);
  add_edge(second, first, 0, -w);
}
int S, T;
long long ans = 0;
int SPFA() {
  static long long dis[max0 + 5];
  static int q[max0 + 5];
  static bool vis[max0 + 5] = {0};
  static int pre[max0 + 5], Min[max0 + 5];
  int head = 0, rear = 0;
  memset(vis, 0, sizeof(vis[0]) * N);
  memset(dis, oo, sizeof(dis[0]) * N);
  q[rear++] = S;
  dis[S] = 0;
  Min[S] = oo;
  while (head != rear) {
    const int &first = q[head++];
    vis[first] = 0;
    if (head >= max0 + 1) head -= max0 + 1;
    for (int i = st[first]; i != -1; i = e[i].nxt) {
      if (!e[i].g) continue;
      const int &second = e[i].id;
      if (chkmin(dis[second], dis[first] + e[i].w)) {
        Min[second] = min(Min[first], e[i].g);
        pre[second] = i;
        if (!vis[second]) {
          vis[second] = 1;
          q[rear++] = second;
          if (rear >= max0 + 1) rear -= max0 + 1;
        }
      }
    }
  }
  if (dis[T] >= 0) return 0;
  int u = T;
  while (u != S) {
    e[pre[u]].g -= Min[T];
    e[pre[u] ^ 1].g += Min[T];
    u = e[pre[u] ^ 1].id;
  }
  ans += dis[T] * Min[T];
  return Min[T];
}
const int maxn = 100, maxm = 100;
int n, m;
int deg[maxn + 5];
int main() {
  memset(st, -1, sizeof st), en = 0;
  scanf("%d%d", &n, &m);
  S = n, T = n + 1;
  N = n + 2;
  ans = 0;
  for (int i = (0), i_end_ = (m); i < i_end_; ++i) {
    int u, v, c, f;
    scanf("%d%d%d%d", &u, &v, &c, &f), --u, --v;
    deg[u] -= f, deg[v] += f;
    if (f > c) {
      ans += abs(c - f);
      add_biedge(u, v, oo, 2);
      add_biedge(v, u, f - c, 0);
      add_biedge(v, u, c, 1);
    } else {
      add_biedge(u, v, c - f, 1);
      add_biedge(u, v, oo, 2);
      add_biedge(v, u, f, 1);
    }
  }
  for (int i = (1), i_end_ = (n - 1); i < i_end_; ++i) {
    ans += (long long)oo * abs(deg[i]);
    if (deg[i] > 0)
      add_biedge(S, i, deg[i], -oo);
    else
      add_biedge(i, T, -deg[i], -oo);
  }
  add_biedge(S, 0, oo, 0);
  add_biedge(S, n - 1, oo, 0);
  add_biedge(0, T, oo, 0);
  add_biedge(n - 1, T, oo, 0);
  while (SPFA())
    ;
  cout << ans << endl;
  return 0;
}
