/**
 * Sergey Kopeliovich (burunduk30@gmail.com)
 */

#include <bits/stdc++.h>
#include "optimization.h"

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()

int main() {
	int n = readInt();
	int m = readInt();

	int maxW = 0;
	vector<int> head(n, -1), x(n);
	vector<int64_t> p(n);
	struct Edge {
		int a, b, f, c, w, next;
		int cf() { return c - f; }
	};
	vector<Edge> es;
	auto cost = [&](int i) { return es[i].w + p[es[i].a] - p[es[i].b]; };

	auto addEdge = [&](int a, int b, int c, int w) {
		if (a == b) return; // no loops!
		maxW = max(maxW, w);
		es.push_back({a, b, 0, c, w, head[a]}), head[a] = es.size() - 1;
		es.push_back({b, a, 0, 0, -w, head[b]}), head[b] = es.size() - 1;
	};

	auto minCost = [&](int s, int t) {
		auto inf = maxW * (n - 1) + 1;
		addEdge(t, s, INT_MAX, -inf); // mincost maxflow -> mincost circulation
		for (auto &e : es)
			e.w *= n + 1;

		auto push = [&](int i, int dx) {
			auto &e = es[i];
			e.f += dx, es[i ^ 1].f -= dx;
			x[e.b] += dx, x[e.a] -= dx;
		};

		const auto ALPHA = 3;
		for (auto EPS = inf; EPS >= 1; ALPHA > EPS && EPS > 1 ? EPS = 1 : EPS /= ALPHA) {
			forn(i, es.size()) 
				if (cost(i) < 0) 
					push(i, es[i].cf());
			for (int run = 1; run; ) {
				run = 0;
				forn(i, n)
					if (x[i] > 0) {
						run = 1;
						for (int j = head[i]; x[i] && j != -1; j = es[j].next)
							if (cost(j) < 0 && es[j].cf())
								push(j, min(es[j].cf(), x[i]));
						if (x[i] > 0) { // relabel
							int best = -1;
							for (int j = head[i]; j != -1; j = es[j].next)
								if (es[j].cf() && (best == -1 || cost(j) < cost(best)))
									best = j;
							p[i] -= cost(best) + EPS;
							push(best, min(es[best].cf(), x[i]));
						}
					}
			}
		}
		int64_t sum = 0;
		forn(i, es.size() - 2)
			if (es[i].f > 0)
				sum += (int64_t)es[i].f * es[i].w;
		return sum / (n + 1);
	};

	while (m--) {
		int a = readInt() - 1;
		int b = readInt() - 1;
		int c = readInt();
		int w = readInt();
		addEdge(a, b, c, w);
	}
	cout << minCost(0, n - 1) << endl;
}