#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct CostFlowEdge {
  const int from, to;
  const int64 cap;
  const int64 cost;
  CostFlowEdge(int from, int to, int64 cap, int64 cost)
      : from(from), to(to), cap(cap), cost(cost) {}
};

// Returns a pair of (flow, cost).
pair<int64, int64> MinCostFlow(
    int n, const vector<CostFlowEdge>& edges, int s, int t, int64 flow_cap) {
  constexpr int64 INF = INT64_MAX / 4;  // Update this when it doesn't work.

  int m = edges.size();
  
  vector<vector<tuple<CostFlowEdge, int>>> graph(n);
  vector<int64> res_caps(2 * m);  // Edge ID to residual cap
  vector<int64> costs(2 * m);  // Edge ID to original cost
  vector<int64> res_costs(2 * m);  // Edge ID to residual cost
  vector<int> to_reverse(2 * m, -1);  // Edge ID to the reverse edge ID

  for (int i = 0; i < m; i++) {
    const auto& edge = edges[i];
    graph[edge.from].push_back(make_tuple(edge, i));
    graph[edge.to].push_back(
        make_tuple(CostFlowEdge(edge.to, edge.from, 0, -edge.cost), m + i));
    res_caps[i] = edge.cap;
    costs[i] = edge.cost;
    costs[m + i] = -edge.cost;
    res_costs[i] = edge.cost;
    res_costs[m + i] = -edge.cost;
    to_reverse[i] = m + i;
    to_reverse[m + i] = i;
  }

  int64 total_flow = 0;
  int64 total_cost = 0;
  struct State {
    int v, parent, last_edge;
    int64 weight;
  };
  auto compare_state = [](State s1, State s2) {
    return s1.weight > s2.weight;
  };
  while (total_flow < flow_cap) {
    priority_queue<State, vector<State>, decltype(compare_state)>
        pq(compare_state);
    pq.push(State({s, -1, -1, 0}));
    vector<int64> distances(n, INF);
    vector<int> parents(n, -1);
    vector<int> last_edges(n, -1);
    vector<int> visited(n);
    while(!pq.empty()) {
      State s = pq.top();
      pq.pop();
      if (visited[s.v]) continue;
      visited[s.v] = true;
      distances[s.v] = s.weight;
      parents[s.v] = s.parent;
      last_edges[s.v] = s.last_edge;
      for (const auto& edge_tuple : graph[s.v]) {
        const auto& edge = get<0>(edge_tuple);
        int edge_id = get<1>(edge_tuple);
        if (res_caps[edge_id] == 0 || visited[edge.to]) continue;
        State next =
            State({edge.to, s.v, edge_id, s.weight + res_costs[edge_id]});
        pq.push(next);
      }
    }

    if (distances[t] == INF) return make_pair(total_flow, total_cost);

    int cur = t;
    vector<int> path;
    while (cur != s) {
      path.push_back(last_edges[cur]);
      cur = parents[cur];
    }

    int64 inc = flow_cap - total_flow;
    for (int edge_id : path) {
      inc = min(inc, res_caps[edge_id]);
    }

    total_flow += inc;

    for (int edge_id : path) {
      total_cost += costs[edge_id] * inc;
      res_caps[edge_id] -= inc;
      res_caps[to_reverse[edge_id]] += inc;
    }

    for (int i = 0; i < m; i++) {
      res_costs[i] += distances[edges[i].from] - distances[edges[i].to];
      res_costs[m + i] -= distances[edges[i].from] - distances[edges[i].to];
    }
  }
  
  return make_pair(total_flow, total_cost);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, m;
  int64 flow_cap;
  cin >> n >> m >> flow_cap;
  vector<CostFlowEdge> edges;
  for (int i = 0; i < m; i++) {
    int v1, v2;
    int64 cap, cost;
    cin >> v1 >> v2 >> cap >> cost;
    edges.push_back(CostFlowEdge(v1, v2, cap, cost));
  }

  int64 flow, cost;
  tie(flow, cost) = MinCostFlow(n, edges, 0, n - 1, flow_cap);
  if (flow == flow_cap) {
    cout << cost << endl;
  } else {
    cout << -1 << endl;
  }
}



Measured memory_bytes: 3292