#include <bits/stdc++.h>
using namespace std;
const int INF(0X3F3F3F3F);
namespace G {
const int Max_V(10000);
const int Max_E(10000);
int V, S, T, Head[Max_V], Total, To[Max_E], Next[Max_E], Cap[Max_E],
    Flow[Max_E], Weight[Max_E];
inline void Add_Edge(int tot, int s, int t, int c, int w) {
  To[tot] = t, Next[tot] = Head[s], Head[s] = tot, Cap[tot] = c, Flow[tot] = 0,
  Weight[tot] = w;
}
inline void Add_Link(int s, int t, int c, int w) {
  Total += 2, Add_Edge(Total, s, t, c, w), Add_Edge(Total ^ 1, t, s, 0, -w);
}
int Dist[Max_V], Cur[Max_V];
bool InQ[Max_V], done[Max_V];
bool SPFA() {
  queue<int> Q;
  for (int i = 1; i <= V; ++i) Dist[i] = 0X3F3F3F3F, InQ[i] = false;
  Dist[S] = 0, Q.push(S), InQ[S] = true;
  for (int u; Q.empty() == false;) {
    InQ[u = Q.front()] = false, Q.pop();
    for (int i = Head[u], v; i; i = Next[i])
      if (Cap[i] > Flow[i] && Dist[v = To[i]] > Dist[u] + Weight[i]) {
        Dist[v] = Dist[u] + Weight[i];
        if (!InQ[v]) Q.push(v), InQ[v] = true;
      }
  }
  return Dist[T] != 0X3F3F3F3F;
}
int DFS(int u, int a) {
  if (u == T || a == 0) return a;
  int Ans(0);
  done[u] = true;
  for (int &i = Cur[u], v, f; i; i = Next[i])
    if (!done[v = To[i]] && Dist[v] == Dist[u] + Weight[i] &&
        (f = DFS(v, min(a, Cap[i] - Flow[i]))) > 0) {
      Ans += f, Flow[i] += f, Flow[i ^ 1] -= f;
      if ((a -= f) == 0) break;
    }
  done[u] = false;
  return Ans;
}
void MCMF(int &COST) {
  for (; SPFA();) {
    for (int i = 1; i <= V; ++i) Cur[i] = Head[i];
    COST += Dist[T] * DFS(S, INF);
  }
}
}  // namespace G
int N, M, S, T, Limit, Ans;
inline void Add_Link(int s, int t, int l, int r, int w) {
  if (r - l) G::Add_Link(s, t, r - l, w);
  if (l) G::Add_Link(G::S, t, l, 0), G::Add_Link(s, G::T, l, 0), Ans += l * w;
}
int main() {
  scanf("%d%d", &N, &M);
  G::V = N + 4, G::S = N + 3, G::T = N + 4, S = N + 1, T = N + 2;
  for (int s, t, c, f; M--;) {
    scanf("%d%d%d%d", &s, &t, &c, &f);
    Add_Link(s, t, f, f, 0);
    if (f <= c) {
      Add_Link(t, s, 0, f, 1);
      Add_Link(s, t, 0, c - f, 1);
      Add_Link(s, t, 0, 1000000, 2);
    } else {
      Ans += f - c;
      Add_Link(t, s, 0, f - c, 0);
      Add_Link(t, s, 0, c, 1);
      Add_Link(s, t, 0, 1000000, 2);
    }
  }
  G::Add_Link(T, S, INF, 0), G::Add_Link(S, 1, INF, 0),
      G::Add_Link(N, T, INF, 0), G::MCMF(Ans);
  printf("%d", Ans);
  return 0;
}
