#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

//const ll INF = 1e9+7;

typedef int Weight;
const Weight INF = 1<<29;
struct Edge{
	int src,dst;
	Weight weight, cap; // weight ???????????????????????¨???
	int rev; // ???????????????
	Edge(int src, int dst, Weight weight=0, Weight cap=0, int rev=-1):
		src(src),dst(dst),weight(weight),cap(cap),rev(rev)
	{}
};
struct Node:public vector<Edge>{};
bool operator<(const Edge &a, const Edge &b){
	return a.weight<b.weight;
}
bool operator>(const Edge &a, const Edge &b){return b<a;}
typedef vector<Node> Graph;
typedef vector<vector<Weight> > Matrix;
//src ?????? dst ?????????????????? cap,?????????cost ???????????°?????????????????????
void add_edge(Graph &G, int src, int dst, Weight cap, Weight cost){
	G[src].push_back(Edge(src,dst,cost,cap,G[dst].size()));
	G[dst].push_back(Edge(dst,src,-cost,0,G[src].size()-1));
}
// O(VE+FElogV)
Weight min_cost_flow(Graph &G,int s,int t,Weight f){
	typedef pair<Weight,int> P;
	Weight res=0;
	int V=G.size();
	vector<Weight> h(V,0);
	vector<int> prevv(V);
	vector<int> preve(V);
	if(s==t)return 0;
	bool start=true;
	while(f>0){
		vector<Weight> dist(V,INF);
		if(start){
			bool update=true;
			dist[s]=0;
			while(update){
				update=false;
				rep(v,V){
					if(dist[v]==INF)continue;
					rep(i,G[v].size()){
						Edge &e=G[v][i];
						if(e.cap>0&&dist[e.dst]>dist[v]+e.weight){
							dist[e.dst]=dist[v]+e.weight;
							prevv[e.dst]=v;
							preve[e.dst]=i;
							update=true;
						}
					}
				}
			}
			start=0;
		}else{
			priority_queue<P,vector<P>,greater<P> > que;
			dist[s]=0;
			que.push(P(0,s));
			while(!que.empty()){
				P p=que.top();que.pop();
				int v=p.second;
				if(dist[v]<p.first)continue;
				for(int i=0;i<(int)G[v].size();i++){
					Edge &e=G[v][i];
					if(e.cap>0&&dist[e.dst]>dist[v]+e.weight+h[v]-h[e.dst]){
						dist[e.dst]=dist[v]+e.weight+h[v]-h[e.dst];
						prevv[e.dst]=v;
						preve[e.dst]=i;
						que.push(P(dist[e.dst],e.dst));
					}
				}
			}
		}
		if(dist[t]==INF){
			return -1;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];
		Weight 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;
}


int main(){
	//ios_base::sync_with_stdio(false);
	int V, E, F;

	cin >> V >> E >> F;
	Graph g(V+1);
	rep(i,E){
		int u, v, c, d;
		cin >> u >> v >> c >> d;
		add_edge(g, u, v, c, d);
	}

	auto ans = min_cost_flow(g, 0, V-1, F);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3176