#include <bits/stdc++.h>
using namespace std;
const int maxn = 20000 + 5;
const int INF = 0x3f3f3f3f;
int vis[maxn];
int dis[maxn], pre[maxn], last[maxn], flow[maxn], maxflow, mincost;
struct Edge {
  int to, next, flow, dis;
} edge[maxn * 2 + 1];
int head[maxn], num_edge;
void init() {
  memset(head, -1, sizeof(head));
  num_edge = -1;
  maxflow = 0;
  mincost = 0;
}
void add_edge(int from, int to, int flow, int dis) {
  edge[++num_edge].next = head[from];
  edge[num_edge].to = to;
  edge[num_edge].flow = flow;
  edge[num_edge].dis = dis;
  head[from] = num_edge;
  edge[++num_edge].next = head[to];
  edge[num_edge].to = from;
  edge[num_edge].flow = 0;
  edge[num_edge].dis = -dis;
  head[to] = num_edge;
}
bool spfa(int s, int t) {
  queue<int> q;
  memset(dis, 0x7f, sizeof(dis));
  memset(flow, 0x7f, sizeof(flow));
  memset(vis, 0, sizeof(vis));
  q.push(s);
  vis[s] = 1;
  dis[s] = 0;
  pre[t] = -1;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    vis[now] = 0;
    for (int i = head[now]; i != -1; i = edge[i].next) {
      if (edge[i].flow > 0 && dis[edge[i].to] > dis[now] + edge[i].dis) {
        dis[edge[i].to] = dis[now] + edge[i].dis;
        pre[edge[i].to] = now;
        last[edge[i].to] = i;
        flow[edge[i].to] = min(flow[now], edge[i].flow);
        if (!vis[edge[i].to]) {
          vis[edge[i].to] = 1;
          q.push(edge[i].to);
        }
      }
    }
  }
  return pre[t] != -1;
}
void MCMF(int s, int t) {
  while (spfa(s, t)) {
    int now = t;
    maxflow += flow[t];
    mincost += flow[t] * dis[t];
    while (now != s) {
      edge[last[now]].flow -= flow[t];
      edge[last[now] ^ 1].flow += flow[t];
      now = pre[now];
    }
  }
}
int main() {
  int n, m, a, b, c, f, ml[maxn], ans = 0;
  init();
  memset(ml, 0, sizeof(ml));
  scanf("%d%d", &n, &m);
  int S = 0, T = n + 1;
  while (m--) {
    scanf("%d%d%d%d", &a, &b, &c, &f);
    if (c < f) {
      mincost += f - c;
      ml[a] += f, ml[b] -= f;
      add_edge(b, a, f - c, 0), add_edge(b, a, c, 1), add_edge(a, b, INF, 2);
    } else {
      ml[a] += f, ml[b] -= f;
      add_edge(a, b, c - f, 1), add_edge(a, b, INF, 2), add_edge(b, a, f, 1);
    }
  }
  add_edge(n, 1, INF, 0);
  for (int i = 1; i <= n; i++) {
    if (ml[i] >= 0) {
      add_edge(i, T, ml[i], 0);
    } else {
      add_edge(S, i, -ml[i], 0);
    }
  }
  MCMF(S, T);
  cout << mincost << endl;
}
