#include <bits/stdc++.h>

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz=" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = 1000000007LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;



class CostFlow
{
public:
    using Cost = ll;
    using Ind = int;
    using Capacity = int;
    using T = ll;  // Total flow

    struct Edge {
        Edge(const Ind from_, const Ind to_, const Ind reverse_, const Capacity capacity_, const Cost cost_, bool is_reverse_ = false) : from{from_}, to{to_}, reverse{reverse_}, capacity{capacity_}, flow{0}, cost{cost_}, is_reverse{is_reverse_} {}
        Ind from;
        Ind to;
        Ind reverse;
        Capacity capacity;
        Capacity flow;
        Cost cost;
        bool is_reverse;
    };

    CostFlow(const Ind v) : V{v}, edge(v), dist(v), pot(v, 0), prev_v(v), prev_e(v) {}

    void addEdge(const Ind from, const Ind to, const Capacity capacity, const Cost cost)
    {
        edge[from].push_back(Edge{from, to, (Ind)edge[to].size(), (Capacity)capacity, (Cost)cost, false});
        edge[to].push_back(Edge{to, from, (Ind)(edge[from].size() - 1), (Capacity)0, (Cost)(-cost), true});
    }

    void calcPotential(const int s)
    {
        fill(pot.begin(), pot.end(), INF<Cost>);
        pot[s] = 0;
        bool no_negative_loop = true;
        for (int i = 0; i < V; i++) {
            for (int v = 0; v < V; v++) {
                if (pot[v] != INF<T>) {
                    for (const auto& e : edge[v]) {
                        if (e.capacity <= 0) {
                            continue;
                        }
                        if (pot[e.to] > pot[v] + e.cost) {
                            pot[e.to] = pot[v] + e.cost;
                            if (i == V - 1) {
                                pot[e.to] = -INF<T>;  // Confirm " -INF < min(possible_cost) * V "
                                no_negative_loop = false;
                            }
                        }
                    }
                }
            }
        }
        if (not no_negative_loop) {
            // なんとかする
        }
    }

    T minCostFlow(const Ind s, const Ind t, T f, const bool calc_pot = false)
    {
        using P = pair<Cost, Ind>;
        T res = 0;
        if (calc_pot) {
            calcPotential(s);
        }
        vector<Cost> potential = pot;
        while (f > 0) {
            priority_queue<P, vector<P>, greater<P>> q;
            fill(dist.begin(), dist.end(), INF<T>);
            dist[s] = 0;
            q.push(make_pair(0, s));
            while (not q.empty()) {
                const P p = q.top();
                q.pop();
                const Ind v = p.second;
                if (dist[v] < p.first) {
                    continue;
                }
                for (Ind i = 0; i < edge[v].size(); i++) {
                    const auto& e = edge[v][i];
                    if (e.capacity > e.flow and dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]) {
                        dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to];
                        prev_v[e.to] = v;
                        prev_e[e.to] = i;
                        q.push(make_pair(dist[e.to], e.to));
                    }
                }
            }
            if (dist[t] == INF<T>) {
                return -1;
                return res;
            }
            for (Ind v = 0; v < V; v++) {
                potential[v] += dist[v];
            }

            T d = f;
            for (Ind v = t; v != s; v = prev_v[v]) {
                const auto& e = edge[prev_v[v]][prev_e[v]];
                d = min(d, (T)(e.capacity - e.flow));
            }
            f -= d;
            res += d * potential[t];
            for (Ind v = t; v != s; v = prev_v[v]) {
                auto& e = edge[prev_v[v]][prev_e[v]];
                e.flow += d;
                edge[v][e.reverse].flow -= d;
            }
        }
        return res;
    }

    const Ind V;
    vector<vector<Edge>> edge;

private:
    vector<Cost> dist;
    vector<Cost> pot;
    vector<Ind> prev_v;
    vector<Ind> prev_e;
};



// Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B
// Status: Accepted

int main()
{
    int V, E;
    ll F;
    std::cin >> V >> E >> F;
    CostFlow f(V);
    for (ll i = 0; i < E; i++) {
        int u, v;
        ll c, d;
        cin >> u >> v >> c >> d;
        f.addEdge(u, v, c, d);
    }
    cout << f.minCostFlow(0, V - 1, F) << endl;
    return 0;
}



Measured memory_bytes: 3268