#include <bits/stdc++.h>
using namespace std;
struct Edge {
  long long c, w;
  int v, next;
} edge[105 * 6 + 105 * 2];
int e, ft[105];
int n, m, S, T, N;
long long INF = 1ll << 60;
long long b[105];
long long dist[105];
bool flag[105];
int pre[105];
int head, tail, qu[105];
void init() {
  memset(ft, -1, sizeof(ft));
  e = 0;
}
void add_edge(int u, int v, long long c, long long w) {
  edge[e].v = v;
  edge[e].w = w;
  edge[e].c = c;
  edge[e].next = ft[u];
  ft[u] = e++;
}
void insert_edge(int u, int v, long long c, long long w) {
  add_edge(u, v, c, w);
  add_edge(v, u, 0ll, -w);
}
bool spfa() {
  for (int i = 0; i < N; i++) {
    dist[i] = INF;
    flag[i] = false;
  }
  head = tail = 0;
  dist[S] = 0ll;
  qu[tail++] = S;
  flag[S] = true;
  while (head != tail) {
    int u = qu[(head++) % (N + 1)];
    for (int i = ft[u]; i != -1; i = edge[i].next) {
      int v = edge[i].v;
      if (edge[i].c == 0) continue;
      long long d = dist[u] + edge[i].w;
      if (d < dist[v]) {
        dist[v] = d;
        pre[v] = i;
        if (!flag[v]) {
          flag[v] = true;
          qu[(tail++) % (N + 1)] = v;
        }
      }
    }
    flag[u] = false;
  }
  return dist[T] < INF;
}
int main() {
  while (scanf("%d%d", &n, &m) == 2) {
    S = 0;
    T = n + 1;
    N = T + 1;
    init();
    memset(b, 0, sizeof(b));
    int u, v, c, f;
    long long sum = 0;
    while (m--) {
      scanf("%d%d%d%d", &u, &v, &c, &f);
      b[u] -= f;
      b[v] += f;
      if (f > c) {
        insert_edge(v, u, (long long)(f - c), 0ll);
        sum += f - c;
        if (c > 0) insert_edge(v, u, (long long)c, 1ll);
        insert_edge(u, v, INF, 2ll);
      } else {
        if (f < c) insert_edge(u, v, (long long)(c - f), 1ll);
        if (f > 0) insert_edge(v, u, (long long)f, 1ll);
        insert_edge(u, v, INF, 2ll);
      }
    }
    insert_edge(n, 1, INF, 0ll);
    for (int i = 1; i <= n; i++) {
      if (b[i] > 0)
        insert_edge(S, i, b[i], 0ll);
      else if (b[i] < 0)
        insert_edge(i, T, -b[i], 0ll);
    }
    while (spfa()) {
      int t = T;
      long long flow = INF;
      while (t != S) {
        flow = min(flow, edge[pre[t]].c);
        t = edge[pre[t] ^ 1].v;
      }
      t = T;
      while (t != S) {
        edge[pre[t]].c -= flow;
        edge[pre[t] ^ 1].c += flow;
        t = edge[pre[t] ^ 1].v;
      }
      sum += flow * dist[T];
    }
    cout << sum << endl;
  }
  return 0;
}
