#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int X = 1e5 + 20;
const int Inf = 1e9 + 7;

struct Edge {
    Edge() = default;
    Edge(int x, int c, int cap, int ind) : to(x), cost(c), capacity(cap), reverse(ind), flow(0) {};

    int to;
    int cost;
    int capacity;
    int reverse;
    int flow;
};

vector<Edge> edges;

vector<int> nec;

vector<vector<int>> g(X);
vector<int> dists(X, Inf);
vector<int> P(X, 0);

int delta(Edge k) {
    return k.capacity - k.flow;
}

void add(int v, int u, int c = 0, int cap = 1, bool isMin = false) {
    Edge x(u, c, cap, edges.size() + 1);
    Edge y(v, -c, 0, edges.size());
    g[v].push_back(edges.size());
    g[u].push_back(edges.size() + 1);
    edges.push_back(x);
    if (isMin) {
        nec.push_back(edges.size() - 1);
    }
    edges.push_back(y);
}

bool dj(int s, int t) {
    dists.assign(X, Inf);
    set<pair<int, int>> d;
    d.insert({0, s});
    dists[s] = 0;
    while (!d.empty()) {
        auto x = *d.begin();
        int v = x.second;
        for (auto to: g[v]) {
            auto &e = edges[to];
            if (delta(e)) {
                int x = dists[v] + e.cost + P[v] - P[e.to];
                if (dists[e.to] > x) {
                    d.erase({dists[e.to], e.to});
                    dists[e.to] = x;
                    d.insert({x, e.to});

                }
            }
        }
        d.erase(d.begin());
    }
    for (int i = 0; i < X; i++) {
        if (dists[i] != Inf) {
            P[i] += dists[i];
        }
    }
    return dists[t] < Inf;
}


int dfsW(int v, int t, vector<bool> &used, int fl = Inf) {
    if (v == t) {
        return fl == Inf ? 0 : fl;
    }
    used[v] = true;
    for (auto to: g[v]) {
        auto &e = edges[to];
        if (!used[e.to] && delta(e) && e.cost + P[v] - P[e.to] == 0) {
            int x = dfsW(e.to, t, used, min(fl, delta(e)));
            if (x) {
                e.flow += x;
                edges[e.reverse].flow -= x;
                return x;
            }
        }
    }
    return 0;
}

pair<int, int> MCMF(int s, int t) {
    vector<bool> used(X, false);
    int ans = 0;
    while (dj(s, t)) {
        dfsW(s, t, used);
        used.assign(X, false);
    }

    for (int i = 0; i < X; i++) {
        for (auto to: g[i]) {
            auto &e = edges[to];
            ans += e.flow * e.cost;
        }
    }

    int flow = 0;
    for (auto x : g[s]) {
        auto k = edges[x];
        flow += k.flow;
    }

    return {flow, ans / 2};
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        int c, l;
        cin >> c >> l;
        add(v, u, 0, l, true);
        add(v, u, 1, c - l);
    }

    auto result = MCMF(1, n);
    for (auto ptr : nec) {
        if (edges[ptr].flow != edges[ptr].capacity) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << result.first << endl;
    return 0;
}