#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <assert.h>
#include <queue>

using namespace std;

// ???(???????????? ????????? ???????????? ???????????????)
struct Edge {
    int to, cap, cost, rev;
    Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {
        assert(this->cap >= 0);
    }
};

class PrimalDual {
public:
    unsigned int V;         // ????????°
    vector<vector<Edge>> G; // ??°???????????£??\???????????¨???

    PrimalDual(unsigned int v): V(v) {
        this->G = vector<vector<Edge>>(v);
    }

    // from??????to??????????????????cap????????????cost???????????°?????????????????????
    void add_edge(int from, int to, int cap, int cost) {
        this->G[from].push_back(Edge(to, cap, cost, (int)this->G[to].size()));      // ???
        this->G[to].push_back(Edge(from, 0, -cost, (int)this->G[from].size() - 1)); // ??????
    }

    // s??????t????????????f???????°??????¨???(??????????????´??????-1)
    int min_cost_flow(int s, int t, int f) {
        vector<int> h(V);               // ??????????????£???
        vector<int> prev_v(V);          // ??´????????????
        vector<int> prev_e(V);          // ??´?????????

        int res = 0;

        while (f > 0) {
            // ????????????????????§h?????´??°??????
            vector<int> dist = vector<int>(this->V, INT_MAX);
            dist[s] = 0;

            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
            que.push(pair<int, int>(0, s)); // first??????????????¢??? second??????????????????

            while (!que.empty()) {
                pair<int, int> p = que.top(); que.pop();
                int v = p.second;
                if (dist[v] < p.first) { continue; }
                for (int i = 0; i < G[v].size(); i++) {
                    Edge &e = G[v][i];
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        prev_v[e.to] = v;
                        prev_e[e.to] = i;
                        que.push(pair<int, int>(dist[e.to], e.to));
                    }
                }
            }
            // ????????\???????????????
            if (dist[t] == INT_MAX) {
                return -1;
            }
            for (int v = 0; v < V; v++) { h[v] += dist[v]; }
            // s-t????????????????????£??????????????????
            int d = f;
            for (int v = t; v != s; v = prev_v[v]) {
                d = min(d, G[prev_v[v]][prev_e[v]].cap);
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prev_v[v]) {
                Edge &e = G[prev_v[v]][prev_e[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int V, E, F;
    cin >> V >> E >> F;
    PrimalDual pd(V);
    for (int i = 0; i < E; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        pd.add_edge(u, v, c, d);
    }

    cout << pd.min_cost_flow(0, V - 1, F) << endl;
    return 0;
}

Measured memory_bytes: 3232