#include <bits/stdc++.h>
using namespace std;
// type {{{
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
// }}}
// macro {{{
// }}}
// debug {{{
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (int i=0; i<(((int)(v).size())); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "(" << p.first << " " << p.second << ")";
}
// }}}
// chmax, chmin {{{
template<class T>
bool chmax(T& a, const T& b) {
    if (a < b) { a = b; return true; }
    return false;
}
template<class T>
bool chmin(T& a, const T& b) {
    if (b < a) { a = b; return true; }
    return false;
}
// }}}
// constants {{{
const ll MOD = 1e9+7;
const ld EPS = 1e-9;
// }}}
/*
template<typename flow_t, typename cost_t>
struct PrimalDual {
    // O(FElogV)
    struct edge {
        int to, rev;
        flow_t cap;
        cost_t cost;
        edge(int to, flow_t cap, cost_t cost, int rev) :
            to(to), cap(cap), cost(cost), rev(rev) {}
    };

    vector<vector<edge>> g;
    const int sz;
    const cost_t INF;

    PrimalDual(int V) : g(V), sz(V), INF(numeric_limits<cost_t>::max()) {}

    void add_edge(int s, int t, flow_t cap, cost_t cost) {
        g[s].emplace_back(t, cap,  cost, (int)g[t].size());
        g[t].emplace_back(s,   0, -cost, (int)g[s].size() - 1);
    }

    void dijkstra(
            vector<cost_t>& dist,
            vector<int>& prevv,
            vector<int>& preve,
            const vector<int>& potential, int s)
    {
        dist.assign(sz, INF);
        prevv.assign(sz, -1);
        preve.assign(sz, -1);
        using Pi = pair<cost_t, int>;
        priority_queue<Pi, vector<Pi>, greater<Pi>> que;
        que.emplace(0, s);
        dist[s] = 0;
        while (!que.empty()) {
            cost_t cost; int v;
            std::tie(cost, v) = que.top();
            que.pop();
            if (dist[v] < cost) continue;
            for (int i = 0; i < g[v].size(); ++i) {
                edge &e = g[v][i];
                cost_t nextCost =
                    dist[v] + e.cost + potential[v] - potential[e.to];
                if (e.cap > 0 and dist[e.to] > nextCost) {
                    dist[e.to] = nextCost;
                    prevv[e.to] = v, preve[e.to] = i;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
    }

    cost_t min_cost_flow(int s, int t, flow_t f) {
        cost_t ret = 0;
        vector<cost_t> potential(sz, 0);

        while (f > 0)
        {
            vector<cost_t> dist;
            vector<int> prevv, preve;
            dijkstra(dist, prevv, preve, potential, s);

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

            for (int v = 0; v < sz; ++v) potential[v] += dist[v];

            flow_t diff = f;
            for (int v = t; v != s; v = prevv[v]) {
                diff = min(diff, g[prevv[v]][preve[v]].cap);
            }
            f -= diff;
            ret += diff * potential[t];

            for (int v = t; v != s; v = prevv[v]) {
                edge &e = g[prevv[v]][preve[v]];
                e.cap -= diff;
                g[v][e.rev].cap += diff;
            }
        }

        return ret;
    }
};
*/
template<typename flow_t, typename cost_t>
struct PrimalDual {
    // O(FElogV)
    struct edge {
        int to, rev;
        flow_t cap;
        cost_t cost;
        edge(int to, flow_t cap, cost_t cost, int rev) :
                to(to), cap(cap), cost(cost), rev(rev) {}
    };
    vector<vector<edge>> g;
    const int sz;
    const cost_t INF;
    PrimalDual(int V, cost_t INF) : g(V), sz(V), INF(INF) {}
    void add_edge(int s, int t, flow_t cap, cost_t cost) {
        g[s].emplace_back(t, cap, cost, (int)g[t].size());
        g[t].emplace_back(s, 0, -cost, (int)g[s].size() - 1);
    }
    void dijkstra(
            vector<cost_t>& dist,
            vector<int>& prevv,
            vector<int>& preve,
            const vector<cost_t>& potential, int s)
    {
        dist.assign(sz, INF);
        prevv.assign(sz, -1);
        preve.assign(sz, -1);
        using Pi = pair<cost_t, int>;
        priority_queue<Pi, vector<Pi>, greater<Pi>> que;
        que.emplace(0, s);
        dist[s] = 0;
        while (!que.empty()) {
            cost_t cost; int v;
            std::tie(cost, v) = que.top();
            que.pop();
            if (dist[v] < cost) continue;
            for (int i = 0; i < g[v].size(); ++i) {
                edge &e = g[v][i];
                if (e.cost == INF or e.cost == -INF) continue;
                cost_t nextCost =
                        dist[v] + e.cost + potential[v] - potential[e.to];
                if (e.cap > 0 and dist[e.to] > nextCost) {
                    dist[e.to] = nextCost;
                    prevv[e.to] = v, preve[e.to] = i;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
    }
    cost_t min_cost_flow(int s, int t, flow_t f) {
        cost_t ret = 0;
        vector<cost_t> potential(sz, 0);
        while (f > 0)
        {
            vector<cost_t> dist;
            vector<int> prevv, preve;
            dijkstra(dist, prevv, preve, potential, s);
            if (dist[t] == INF) return -1;
            for (int v = 0; v < sz; ++v) potential[v] += dist[v];
            flow_t diff = f;
            for (int v = t; v != s; v = prevv[v]) {
                diff = min(diff, g[prevv[v]][preve[v]].cap);
            }
            f -= diff;
            ret += diff * potential[t];
            for (int v = t; v != s; v = prevv[v]) {
                edge &e = g[prevv[v]][preve[v]], &re = g[v][e.rev];
                e.cap -= diff;
                re.cap += diff;
            }
        }
        return ret;
    }
};
int main() {
    int n, m, f; cin >> n >> m >> f;
    PrimalDual<int,int> graph(n, numeric_limits<int>::max());
    for (int i = 0; i < m; ++i) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        graph.add_edge(u, v, c, d);
    }
    int ans = graph.min_cost_flow(0, n-1, f);
    cout << ans << endl;
}


Measured memory_bytes: 3160