#include <bits/stdc++.h>
using namespace std;

using Flow = int;
using Cost = int;
const int MAX_V = 100000;
const auto INF = numeric_limits<Flow>::max() / 8;

struct PrimalDual {
    struct Edge {
        int dst;
        Flow cap, flow;
        Cost cost;
        int rev, is_rev;
        Edge(int dst, Flow cap, Flow flow, Cost cost, int rev, bool is_rev)
            :dst(dst), cap(cap), flow(flow), cost(cost), rev(rev), is_rev(is_rev) {}
    };

    int n;
    vector<vector<Edge> > g;
    PrimalDual(int n_) : n(n_), g(vector<vector<Edge> >(n_)){}

    void add_edge(int src, int dst, Flow cap, Cost cost) { // ?????????
        int rsrc = g[dst].size();
        int rdst = g[src].size();
        g[src].emplace_back(dst, cap, 0,    cost,  rsrc, false);
        g[dst].emplace_back(src, cap, cap, -cost, rdst, true);
    }

    Cost solve(int s, int t, Flow f) {
        Cost res = 0;

        static Cost h[MAX_V+10], dist[MAX_V];
        static int prevv[MAX_V+10], preve[MAX_V+10];
        // vector<Cost> h(g.size()), dist(g.size());
        // vector<int> prevv(g.size()), preve(g.size());

        using pcv = pair<Cost,int>;
        priority_queue<pcv, vector<pcv>, greater<pcv> > q;
        fill(h, h+n, 0);
        while (f > 0) {
            fill(dist, dist+n, INF);
            dist[s] = 0;
            q.emplace(0, s);
            while (q.size()) {
                Cost cd; int v;
                tie(cd, v) = q.top();
                q.pop();
                if (dist[v] < cd) continue;
                for (int i = 0; i < (int)(g[v].size()); ++i){
                    Edge &e = g[v][i];
                    if (residue(e) == 0) continue;
                    if (dist[e.dst] + h[e.dst] > cd + h[v] + e.cost) {
                        dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
                        prevv[e.dst] = v;
                        preve[e.dst] = i;
                        q.emplace(dist[e.dst], e.dst);
                    }
                }
            }

            if (dist[t] == INF) return -1; // ?????????????????????????????£???

            // s-t ????????????????????£??????????????????
            for (int i = 0; i < n; ++i) h[i] += dist[i];
            Flow d = f;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, residue(g[prevv[v]][preve[v]]));
            }
            f -= d;
            res += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = g[prevv[v]][preve[v]];
                e.flow += d;
                g[v][e.rev].flow -= d;
            }
            
        }
        return res;
    }

    Flow residue(const Edge &e){ return e.cap - e.flow; }

    // ?????? = ??????????????? - ?????¨??????????????¨???
    void show(){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < (int)(g[i].size()); ++i){
                Edge &e = g[i][j];
                if(e.is_rev) continue;
                printf("%3d->%3d (flow:%d)\n", i, e.dst, e.flow);
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, f;
    cin >> n >> m >> f;
    PrimalDual pd(n);
    for (int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        pd.add_edge(u, v, c, d);
    }
    cout << pd.solve(0, n - 1, f) << endl;
}

Measured memory_bytes: 3280