#include <bits/stdc++.h>
using namespace std;
struct MinCostFlow {
  bool iszerocap(long long cap) { return cap == 0; }
  struct edge {
    int target;
    long long cost;
    long long residual_capacity;
    long long orig_capacity;
    size_t revid;
  };
  int n;
  vector<vector<edge>> graph;
  vector<long long> pi;
  bool needNormalize, ranbefore;
  int lastStart;
  MinCostFlow(int n)
      : graph(n), n(n), pi(n, 0), needNormalize(false), ranbefore(false) {}
  void addEdge(int s, int e, long long cost, long long cap) {
    if (s == e) return;
    edge forward = {e, cost, cap, cap, graph[e].size()};
    edge backward = {s, -cost, 0, 0, graph[s].size()};
    if (cost < 0 || ranbefore) needNormalize = true;
    graph[s].emplace_back(forward);
    graph[e].emplace_back(backward);
  }
  bool normalize(int s) {
    auto infinite_cost = numeric_limits<long long>::max();
    vector<long long> dist(n, infinite_cost);
    dist[s] = 0;
    queue<int> q;
    vector<int> v(n), relax_count(n);
    v[s] = 1;
    q.push(s);
    while (!q.empty()) {
      int cur = q.front();
      v[cur] = 0;
      q.pop();
      if (++relax_count[cur] >= n) return false;
      for (const auto &e : graph[cur]) {
        if (iszerocap(e.residual_capacity)) continue;
        auto next = e.target;
        auto ncost = dist[cur] + e.cost;
        if (dist[next] > ncost) {
          dist[next] = ncost;
          if (v[next]) continue;
          v[next] = 1;
          q.push(next);
        }
      }
    }
    for (int i = 0; i < n; i++) pi[i] = dist[i];
    return true;
  }
  pair<long long, long long> AugmentShortest(int s, int e,
                                             long long flow_limit) {
    auto infinite_cost = numeric_limits<long long>::max();
    auto infinite_flow = numeric_limits<long long>::max();
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        pq;
    vector<pair<long long, long long>> dist(n, make_pair(infinite_cost, 0));
    vector<int> from(n, -1), v(n);
    if (needNormalize || (ranbefore && lastStart != s)) normalize(s);
    ranbefore = true;
    lastStart = s;
    dist[s] = pair<long long, long long>(0, infinite_flow);
    pq.emplace(dist[s].first, s);
    while (!pq.empty()) {
      auto cur = pq.top().second;
      pq.pop();
      if (v[cur]) continue;
      v[cur] = 1;
      if (cur == e) continue;
      for (const auto &e : graph[cur]) {
        auto next = e.target;
        if (v[next]) continue;
        if (iszerocap(e.residual_capacity)) continue;
        auto ncost = dist[cur].first + e.cost - pi[next] + pi[cur];
        auto nflow = min(dist[cur].second, e.residual_capacity);
        if (dist[next].first <= ncost) continue;
        dist[next] = make_pair(ncost, nflow);
        from[next] = e.revid;
        pq.emplace(dist[next].first, next);
      }
    }
    auto p = e;
    auto pathcost = dist[p].first + pi[p] - pi[s];
    auto flow = dist[p].second;
    if (iszerocap(flow) || (flow_limit <= 0 && pathcost >= 0))
      return pair<long long, long long>(0, 0);
    if (flow_limit > 0) flow = min(flow, flow_limit);
    for (int i = 0; i < n; i++) {
      if (iszerocap(dist[i].second)) continue;
      pi[i] += dist[i].first;
    }
    while (from[p] != -1) {
      auto nedge = from[p];
      auto np = graph[p][nedge].target;
      auto fedge = graph[p][nedge].revid;
      graph[p][nedge].residual_capacity += flow;
      graph[np][fedge].residual_capacity -= flow;
      p = np;
    }
    return make_pair(pathcost * flow, flow);
  }
  pair<long long, long long> solve(
      int s, int e, long long flow_minimum = numeric_limits<long long>::max()) {
    long long total_cost = 0;
    long long total_flow = 0;
    for (;;) {
      auto res = AugmentShortest(s, e, flow_minimum - total_flow);
      if (res.second <= 0) break;
      total_cost += res.first;
      total_flow += res.second;
    }
    return make_pair(total_cost, total_flow);
  }
};
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<long long> net_vsum(n);
  int source = n, sink = n + 1;
  MinCostFlow mcf(n + 2);
  long long baseval = 0;
  for (int i = 0; i < m; i++) {
    int u, v, c, f;
    scanf("%d%d%d%d", &u, &v, &c, &f);
    u--, v--;
    if (f <= c) {
      net_vsum[u] -= f;
      net_vsum[v] += f;
      mcf.addEdge(u, v, 1, c - f);
      mcf.addEdge(u, v, 2, LLONG_MAX / 100);
      mcf.addEdge(v, u, 1, f);
    } else {
      net_vsum[u] -= c;
      net_vsum[v] += c;
      baseval += f - c;
      mcf.addEdge(u, v, 0, f - c);
      mcf.addEdge(u, v, 2, LLONG_MAX / 100);
      mcf.addEdge(v, u, 1, c);
    }
  }
  for (int i = 0; i < n; i++) {
    if (net_vsum[i] > 0) {
      mcf.addEdge(source, i, 0, net_vsum[i]);
    } else if (net_vsum[i] < 0) {
      mcf.addEdge(i, sink, 0, -net_vsum[i]);
    }
  }
  mcf.addEdge(n - 1, 0, 0, LLONG_MAX / 100);
  long long ans = mcf.solve(source, sink).first;
  ans += baseval;
  printf("%lld\n", ans);
  return 0;
}
