#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int N = 100;

struct Edge {
  int from, to, f, c, cost;
};

vector<Edge> e;
vector<int> edges[N];
long long ans;
int s, t, n, m, d[N], p[N];

void add( int a, int b, int c, int w ) {
  edges[a].push_back(e.size());
  e.push_back({a, b, 0, c, w});
}

const int INF = 1e9;

bool fb() {
  forn(i, n)
    d[i] = INF;
  d[s] = 0;
  //forn(_, n) {
  for (int run = 1; run; ) {
    run = 0;
    forn(i, e.size()) {
      auto &edge = e[i];
      if (d[edge.from] != INF && edge.f < edge.c && d[edge.to] > d[edge.from] + edge.cost) {
        d[edge.to] = d[edge.from] + edge.cost;
        p[edge.to] = i;
        run = 1;
      }
    }
  }
  return d[t] != INF;
}

void relax() {
  int mi = INF;
  for (int v = t; v != s; v = e[p[v]].from) {
    int i = p[v];
    mi = min(mi, e[i].c - e[i].f);
  }
  for (int v = t; v != s; v = e[p[v]].from) {
    int i = p[v];
    e[i].f += mi, e[i ^ 1].f -= mi;
    ans += (long long)e[i].cost * mi;
  }     
}

int main() {
  cin >> n >> m;
  while (m--) {
    int a, b, c, w;
    cin >> a >> b >> c >> w, a--, b--;
    add(a, b, c, w);  // 2i
    add(b, a, 0, -w); // 2i+1
  }
  s = 0, t = n - 1;
  while (fb()) 
    relax();
  cout << ans << endl;
}