#include <bits/stdc++.h>
#define int long long int
#define MOD(x) ((x % MOD_N) + MOD_N) % MOD_N
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,v) for(auto i=v.begin();i!=v.end();++i)
#define REACH(i,v) for(auto i=v.rbegin();i!=v.rend();++i)
#define LB(c,x) distance((c).begin(),lower_bound(ALL(c),x))
#define UB(c,x) distance((c).begin(),upper_bound(ALL(c),x))
#define COUNT(c,x) (lower_bound(ALL(c),x)-upper_bound(ALL(c),x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DUMP(x)  cerr<<#x<<" = "<<(x)<<endl;
#define NL cerr<<endl;
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T sum(vector<T>&v){return accumulate(ALL(v),T());}
template<typename T>T sum(vector<T>&v,int a,int b){return accumulate(v.begin()+a,v.begin()+b,T());}
template<typename T>T max(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T min(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T max_index(vector<T>&v){return distance((v).begin(),max_element(ALL(v)));}
template<typename T>T min_index(vector<T>&v){return distance((v).begin(),min_element(ALL(v)));}

template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}

const int INF = 1e18;
const int MOD_N = 1e9+7;

struct edge { int to, rev, cap, cost; };
void add_edge(vector<vector<edge>>& G, int u, int v, int c, int d) {
   G[u].push_back((edge){ v, SZ(G[v])  , c,  d });
   G[v].push_back((edge){ u, SZ(G[u])-1, 0, -d });
}
template<typename T>
void dijkstra(const vector< vector<edge> >& G, vector<T>& d, const V<int>& h, V<int>& prevv, V<int>& preve, int s)
{
   priority_queue<P<T,int>, vector<P<T,int>>, greater<P<T,int>> > que;
   fill(d.begin(), d.end(), INF);
   d[s] = 0;
   que.push(make_pair(0, s));
   while(!que.empty()) {
      T temp_cost = que.top().first;
      int v = que.top().second;
      que.pop();
      if (d[v] < temp_cost) continue;
      for (int i = 0; i < G[v].size(); i++) {
         const edge& e = G[v][i];
         if (e.cap > 0 && d[e.to] > d[v] + e.cost + h[v] - h[e.to]) {
            d[e.to] = d[v] + e.cost + h[v] - h[e.to];
            prevv[e.to] = v;
            preve[e.to] = i;
            que.push(make_pair(d[e.to], e.to));
         }
      }
   }
}
int min_cost_flow(const V<V<edge>>& g, int s, int t, int f) {
   V<V<edge>> G(g);
   int N = G.size();
   V<int> h(N, 0), prevv(N,-1), preve(N,-1);
   int res = 0;
   while (f > 0) {
      V<int> dist(N);
      dijkstra(G, dist, h, prevv, preve, s);
      if (dist[t] == INF) return -1;
      for (int v = 0; v < N; v++) h[v] += dist[v];
      int d = f;
      for (int v = t; v != s; v = prevv[v]) {
         d = min(d, G[prevv[v]][preve[v]].cap);
      }
      f -= d;
      res += d * h[t];
      for (int v = t; v != s; v = prevv[v]) {
         edge& e = G[prevv[v]][preve[v]];
         e.cap -= d;
         G[v][e.rev].cap += d;
      }
   }
   return res;
}

signed main()
{
   int n, m, f; cin >> n >> m >> f;
   V<V<edge>> G(n);
   REP(i, m) {
      int u, v, c, d; cin >> u >> v >> c >> d;
      add_edge(G, u, v, c, d);
   }
   int ans = min_cost_flow(G, 0, n-1, f);
   cout << ans << endl;

   return 0;
}



Measured memory_bytes: 3244