#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

const int INF = 1 << 29;

// (P) Minimize obj = sum(Cost[lk] * flow[lk], lk < Link)
//     subject to
//         [1] 0 <= flow[lk] <= Capa[lk]
//         [2] sum(flow[lk], to(lk) == nd) == sum(flow[lk], fr(lk) == nd)
//             for each nd != s, t
//         [3] sum(flow[lk], fr(lk) == s) == F
//         [4] sum(flow[lk], to(lk) == t) == F

void print_adjacency_list(const vector< vector< tuple<int, int, int, int> > > &adj)
{
  cout << "st_nd: (ed_nd, capa, cost, st_ind), ..." << endl;
  for (int st_nd = 0; st_nd < adj.size(); ++st_nd) {
    cout << st_nd << ":";
    for (auto itr = adj[st_nd].begin(); itr != adj[st_nd].end(); ++itr) {
      int ed_nd, capa, cost, st_ind; tie(ed_nd, capa, cost, st_ind) = *itr;
      cout << " (" << ed_nd << ", " << capa
           << ", " << cost << ", " << st_ind << ")";
    }
    cout << endl;
  }
}

int min_cost_flow(const int src_nd, const int sink_nd, const int flow_vol,
                  vector< vector< tuple<int, int, int, int> > > adj)
{
  int flow_res = flow_vol;  
  int min_cost = 0;
  int n_nodes = adj.size();
  while (flow_res > 0) {
    // Finding s-t path by Bellman-Ford Algorithm
    vector<int> dist(n_nodes, INF);
    vector< pair<int, int> > pred(n_nodes, make_pair(-1, -1)); // (pre_nd, nd_ind)
    dist[src_nd] = 0;
    bool relax = true;
    while (relax) {
      relax = false;
      for (int st_nd = 0; st_nd < n_nodes; ++st_nd) {
        if (dist[st_nd] == INF) { continue; }
        for (int ed_ind = 0; ed_ind < adj[st_nd].size(); ++ed_ind) { 
          int ed_nd, capa, cost; tie(ed_nd, capa, cost, ignore) = adj[st_nd][ed_ind];
          if (capa > 0 && dist[st_nd] + cost < dist[ed_nd]) {
            dist[ed_nd] = dist[st_nd] + cost;
            pred[ed_nd] = make_pair(st_nd, ed_ind);
            relax = true;
          }
        }
      }
    }
    // Infeasible
    if (dist[sink_nd] == INF) { return -1; }
    // Flow along s-t path
    int flow = flow_res; 
    for (int nd = sink_nd; nd != src_nd; nd = get<0>(pred[nd])) {
      int pre_nd, nd_ind; tie(pre_nd, nd_ind) = pred[nd];
      flow = min(flow, get<1>(adj[pre_nd][nd_ind]));
    }
    flow_res -= flow;    
    min_cost += dist[sink_nd] * flow;
    for (int nd = sink_nd; nd != src_nd; nd = get<0>(pred[nd])) {
      int pre_nd, nd_ind; tie(pre_nd, nd_ind) = pred[nd];
      int &capa = get<1>(adj[pre_nd][nd_ind]);
      int pre_ind; tie(ignore, ignore, ignore, pre_ind) = adj[pre_nd][nd_ind];
      int &rev_capa = get<1>(adj[nd][pre_ind]);
      capa -= flow;
      rev_capa += flow;
    }
  }
  return min_cost;
}

int main(int argc, char *argv[])
{
  int n_nodes, n_links, flow_vol;
  cin >> n_nodes >> n_links >> flow_vol;
  vector< vector< tuple<int, int, int, int> > > adj(n_nodes);
  for (int lk = 0; lk < n_links; ++lk) {
    int st_nd, ed_nd, capa, cost;
    cin >> st_nd >> ed_nd >> capa >> cost;
    adj[st_nd].push_back(make_tuple(ed_nd, capa, cost, adj[ed_nd].size()));
    adj[ed_nd].push_back(make_tuple(st_nd, 0, -cost, adj[st_nd].size() - 1));
  }

  // print_adjacency_list(adj);
  
  int src_nd = 0;
  int sink_nd = n_nodes - 1;
  cout << min_cost_flow(src_nd, sink_nd, flow_vol, adj) << endl;
  
  return 0;
}

Measured memory_bytes: 3180