// ???????????????????????????

#include<algorithm>
#include<cfloat>
#include<functional>
#include<queue>
#include<vector>

using Vertex = int;
using Flow   = long double;
using Cost   = long double;

const Flow FLOW_INF = LDBL_MAX;
const Cost COST_INF = LDBL_MAX;

struct Edge {
  Vertex from, to;
  Flow capacity;
  Cost cost;
  int rev;
  Edge(Vertex from, Vertex to, Flow capacity = 0, Cost cost = 0, int rev = -1) : from(from), to(to), capacity(capacity), cost(cost), rev(rev) {}
};

class FlowNetwork {
 public:
  FlowNetwork(int n);
  void insert(const Edge&);
  Flow maximum_flow(Vertex source, Vertex sink) const;
  Cost minimum_cost_flow(Vertex source, Vertex sink, Flow f) const;
 private:
  Vertex size_;
  std::vector<std::vector<Edge>> edge_;
};

// ?????????????????????
FlowNetwork::FlowNetwork(int n) : size_(n), edge_(n) {}

// ????????????
//   ????????¨????????????0?????????-c????????????????????????
void FlowNetwork::insert(const Edge& e) {
  edge_.at(e.from).emplace_back(e.from, e.to, e.capacity, e.cost, edge_.at(e.to).size());
  edge_.at(e.to).emplace_back(e.to, e.from, 0, -e.cost, edge_.at(e.from).size() - 1);
}

// ?????§???
//   Dinic: O(|V|^2 * |E|)
Flow FlowNetwork::maximum_flow(Vertex source, Vertex sink) const {
  std::vector<int> level;   // ?????????????????????source??????????????¢
  std::vector<int> itr;     // ????????????????????????itr[v]????????\?????????????????£??????????§?
  auto residue = edge_;     // ????????°??????
  // source????????????????????§????????¢????¨??????????sink?????§????????¢?????????
  auto bfs = [&]() {
    level.assign(size_, -1);
    level.at(source) = 0;
    std::queue<int> q;
    q.push(source);
    while(!q.empty()) {
      auto v = q.front();
      q.pop();
      for(const auto& e: residue.at(v)) if(!~level.at(e.to)) if(0 < e.capacity) {
        level.at(e.to) = level.at(e.from) + 1;
        q.push(e.to);
      }
    }
    return level.at(sink);
  };
  // ?????????????????????????????¨????????????????????????
  std::function<Flow(Vertex, Flow)> dfs = [&](Vertex v, Flow cur) {
    if(v == sink) return cur;
    for(auto& i = itr.at(v); i < residue.at(v).size(); ++i) {
      auto& e = residue.at(v).at(i);
      if(level.at(e.from) < level.at(e.to)) if(0 < e.capacity) {
        auto f = dfs(e.to, std::min(cur, e.capacity));
        if(f == 0) continue;
        e.capacity -= f;
        residue.at(e.to).at(e.rev).capacity += f;
        return f;
      }
    }
    return Flow(0);
  };
  // Dinic
  Flow result = 0;
  while(~bfs()) {
    itr.assign(size_, 0);
    while(auto f = dfs(source, FLOW_INF)) result += f;
  }
  return result;
}

// ????°??????¨???
//   Primal-Dual: O(|V|^2 * U * C)
Cost FlowNetwork::minimum_cost_flow(Vertex source, Vertex sink, Flow f) const {
  std::vector<Cost> h(size_, 0);
  auto residue = edge_;
  Flow result = 0;
  while(0 < f) {
    // source??????Dijkstra
    using Node = std::tuple<Cost, Vertex>;
    std::vector<Cost> dist(size_, COST_INF);
    dist.at(source) = 0;
    std::vector<Edge*> prev(size_, nullptr);
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> q;
    q.emplace(0, source);
    while(!q.empty()) {
      Cost c; Vertex v;
      std::tie(c, v) = q.top();
      q.pop();
      if(dist.at(v) < c) continue;
      for(auto& e: residue.at(v)) {
        if(e.capacity <= 0) continue;
        if(dist.at(e.to) <= dist.at(e.from) + e.cost + h.at(e.from) - h.at(e.to)) continue;
        dist.at(e.to) = dist.at(e.from) + e.cost + h.at(e.from) - h.at(e.to);
        prev.at(e.to) = &e;
        q.emplace(dist.at(e.to), e.to);
      }
    }
    // sink?????§?????????????????¨??????????????°??????
    if(dist.at(sink) == COST_INF) return -1;
    // ???????????¢?????´??°
    for(int v = 0; v < size_; ++v) if(dist.at(v) != COST_INF) h.at(v) += dist.at(v);
    // ?????????????????????
    Flow add = f;
    for(Vertex v = sink; v != source; v = prev.at(v)->from) add = std::min(add, prev.at(v)->capacity);
    f -= add;
    result += add * h.at(sink);
    for(Vertex v = sink; v != source; v = prev.at(v)->from) {
      prev.at(v)->capacity -= add;
      residue.at(prev.at(v)->to).at(prev.at(v)->rev).capacity += add;
    }
  }
  return result;
}

#include<bits/stdc++.h>
using namespace std;
int main() {
//   // GRL_6_A
//   int V, E;
//   cin >> V >> E;
//   FlowNetwork G(V);
//   for(int i = 0; i < E; ++i) {
//     Vertex u, v; Flow c;
//     cin >> u >> v >> c;
//     G.insert(Edge(u, v, c));
//   }
//   cout << G.maximum_flow(0, V - 1) << endl;
  // GRL_6_B
  int V, E, F;
  cin >> V >> E >> F;
  FlowNetwork G(V);
  for(int i = 0; i < E; ++i) {
    Vertex u, v; Flow c; Cost d;
    cin >> u >> v >> c >> d;
    G.insert({u, v, c, d});
  }
  cout << G.minimum_cost_flow(0, V - 1, F) << endl;
}

Measured memory_bytes: 3384