#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

class WeightedFlowNetwork {
  struct Edge {
    int from;
    int to;
    int64_t capacity;
    int64_t flow;
    int64_t cost;
  };

  vector<vector<int>> outEdge, inEdge;
  vector<Edge> edgeData;
  vector<int> potential;

 public:
  WeightedFlowNetwork(const int size)
      : outEdge(size), inEdge(size), potential(size, 0) {}

  void addEdge(const int from, const int to, const int64_t capacity,
               const int64_t cost) {
    const int eId = edgeData.size();
    Edge eData;
    eData.from = from;
    eData.to = to;
    eData.flow = 0;
    eData.capacity = capacity;
    eData.cost = cost;
    edgeData.push_back(eData);
    outEdge[from].push_back(eId);
    inEdge[to].push_back(eId);
  }

  pair<int64_t, int64_t> maxflow(const int source, const int sink,
                                 const int64_t f) {
    const int n = outEdge.size();
    int64_t demand = f;

    while (true) {
      // check if reachable to sink
      const int64_t INF = 1'000'000'000;
      using P = pair<int64_t, int>;
      vector<int> parent(n, -1);
      vector<int64_t> dist(n, INF);
      priority_queue<P, vector<P>, greater<P>> q;

      dist[source] = 0;
      q.push(P(0, source));

      while (!q.empty()) {
        int64_t d;
        int v;
        tie(d, v) = q.top();
        q.pop();

        if (d > dist[v]) {
          continue;
        }

        for (const int e : outEdge[v]) {
          const Edge &data = edgeData[e];
          const int nv = data.to;
          const int64_t nd = d + data.cost + potential[v] - potential[nv];
          if (dist[nv] > nd && data.capacity - data.flow > 0) {
            q.push(P(nd, nv));
            dist[nv] = nd;
            parent[nv] = e;
          }
        }

        for (const int e : inEdge[v]) {
          const Edge &data = edgeData[e];
          const int nv = data.from;
          const int64_t nd = d - data.cost + potential[v] - potential[nv];
          if (dist[nv] > nd && data.flow > 0) {
            q.push(P(nd, nv));
            dist[nv] = nd;
            parent[nv] = e;
          }
        }
      }

      for (int i = 0; i < potential.size(); i++) potential[i] += dist[i];

      if (parent[sink] < 0 || demand == 0) {
        break;
      }

      // select path from source to sink
      int64_t fDiff = demand;
      int v = sink;
      while (v != source) {
        const int e = parent[v];
        const Edge &data = edgeData[e];
        if (data.to == v) {
          fDiff = min(fDiff, data.capacity - data.flow);
          v = data.from;
        } else {
          fDiff = min(fDiff, data.flow);
          v = data.to;
        }
      }

      // update flow on the path
      v = sink;
      while (v != source) {
        const int e = parent[v];
        Edge &data = edgeData[e];
        if (data.to == v) {
          data.flow += fDiff;
          v = data.from;
        } else {
          data.flow -= fDiff;
          v = data.to;
        }
      }

      demand -= fDiff;
    }

    int64_t rCost = 0;
    for (const Edge &eData : edgeData) {
      rCost += eData.cost * eData.flow;
    }
    return pair<int64_t, int64_t>(f - demand, rCost);
  }
};

int main() {
  int V, E, F;
  cin >> V >> E >> F;

  WeightedFlowNetwork net(V);

  rep(i, E) {
    int u, v, c, d;
    cin >> u >> v >> c >> d;
    net.addEdge(u, v, c, d);
  }

  int64_t f, cost;
  tie(f, cost) = net.maxflow(0, V - 1, F);
  cout << (f < F ? -1 : cost) << endl;
  return 0;
}


Measured memory_bytes: 3212