#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:255000000")
bool firstout = 1;
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
void err(vector<string>::iterator it) {}
template <typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
  cout << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n';
  err(++it, args...);
}
template <class T>
T &minn(T &a, T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
T &maxx(T &a, T b) {
  if (a < b) a = b;
  return a;
}
int &madd(int &a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
int &msub(int &a, int b) {
  a -= b;
  if (a < 0) a += 1000000007;
  return a;
}
int &mmult(int &a, int b) { return a = (long long)a * b % 1000000007; }
int mdiv(long long a, long long b, long long m) {
  a = (a % m + m) % m;
  b = (b % m + m) % m;
  if (a % b == 0) return a / b;
  return (a + m * mdiv(-a, m, b)) / b;
}
struct edge {
  int i, c, a, ii;
  edge(int _i, int _c, int _a, int _ii) {
    i = _i;
    c = _c;
    a = _a;
    ii = _ii;
  }
};
int nt;
vector<edge> F[10123];
bool FB[10123];
int FD[10123];
int FDP[10123];
int FDK[10123];
void init() { nt = 0; }
int addNode() {
  F[nt].clear();
  return nt++;
}
void addEdge(int i, int j, int c, int a) {
  if (c <= 0) return;
  int ii = F[i].size();
  int jj = F[j].size();
  F[i].push_back(edge(j, c, a, jj));
  F[j].push_back(edge(i, 0, -a, ii));
}
int curl(int i0, int c) {
  int i, j, k;
  for (i = 0; i < nt; ++i) FD[i] = 1012345678;
  FD[i0] = 0;
  FDP[i0] = -1;
  set<pair<int, int> > s;
  s.insert(make_pair(0, i0));
  for (; s.size();) {
    i = s.begin()->second;
    s.erase(s.begin());
    for (k = 0; k < F[i].size(); ++k)
      if (F[i][k].c >= c) {
        j = F[i][k].i;
        int a = FD[i] + F[i][k].a;
        if (a < FD[j]) {
          bool b = FD[j] < 1012345678;
          s.erase(make_pair(FD[j], j));
          FD[j] = a;
          FDP[j] = i;
          FDK[j] = k;
          if (b) {
            int p = i;
            for (; p != -1 && p != j; p = FDP[p])
              ;
            if (p == j) return j;
          }
          s.insert(make_pair(FD[j], j));
        }
      }
  }
  return -1;
}
int curlp(int i0, int c) {
  int i, j, k;
  for (i = 0; i < nt; ++i) FD[i] = 1012345678, FB[i] = 0;
  FD[i0] = 0;
  FDP[i0] = -1;
  for (;;) {
    bool b = 0;
    for (i = 0; i < nt; ++i)
      if (!FB[i] && FD[i] < 1012345678) {
        b = 1;
        FB[i] = 1;
        for (k = 0; k < F[i].size(); ++k)
          if (F[i][k].c >= c) {
            j = F[i][k].i;
            int a = FD[i] + F[i][k].a;
            if (a < FD[j]) {
              bool b = FD[j] < 1012345678;
              FD[j] = a;
              FDP[j] = i;
              FDK[j] = k;
              FB[j] = 0;
              if (b) {
                int p = i;
                for (; p != -1 && p != j; p = FDP[p])
                  ;
                if (p == j) return j;
              }
            }
          }
      }
    if (!b) break;
  }
  return -1;
}
long long minCostCurl(int c) {
  int i, j, k, s;
  long long res = 0;
  for (;;) {
    for (i = 0; i < nt; ++i)
      if ((s = curlp(i, c)) >= 0) break;
    if (i == nt) break;
    bool f = 1;
    long long r = 0;
    for (j = s; j != s || f; j = i) {
      f = 0;
      i = FDP[j];
      k = FDK[j];
      r += c * F[i][k].a;
    }
    if (r >= 0) break;
    f = 1;
    for (j = s; j != s || f; j = i) {
      f = 0;
      i = FDP[j];
      k = FDK[j];
      res += c * F[i][k].a;
      F[i][k].c -= c;
      F[j][F[i][k].ii].c += c;
    }
  }
  return res;
}
int n, m;
int main() {
  int i, j, k;
  char c;
  int a, d;
  int ts;
  for (ts = 1; scanf("%"
                     "d",
                     &(n)) > 0;
       ++ts) {
    scanf(
        "%"
        "d",
        &(m));
    init();
    for (i = (0); i < (n); ++i) addNode();
    addEdge(n - 1, 0, 101234567, 0);
    long long res = 0;
    for (k = (0); k < (m); ++k) {
      int c, f;
      scanf(
          "%"
          "d",
          &(i));
      scanf(
          "%"
          "d",
          &(j));
      scanf(
          "%"
          "d",
          &(c));
      scanf(
          "%"
          "d",
          &(f));
      --i;
      --j;
      addEdge(i, j, min(c, f), -1);
      addEdge(i, j, f - c, 0);
      addEdge(i, j, c - f, 1);
      addEdge(i, j, 101234567 - max(c, f), 2);
      res += f;
    }
    int c = 101234567;
    for (; c > 0; c /= 2) {
      res += minCostCurl(c);
    }
    printf(
        "%"
        "I64d",
        (res));
    printf("\n"), firstout = 1;
  }
  return 0;
}
