#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN (-2147483647 - 1)
#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> P;



class Networkflow {
private:
	struct edgedata {
		int from, to, capacity, weight;
		edgedata* dual_p;
		bool operator<(const edgedata & another) const {
			return (weight != another.weight ? weight < another.weight : capacity > another.capacity);
		}
	};
	struct node {
		int id, d;
		bool done;
		edgedata* fromedge_p;
		list<edgedata> edges;
		bool operator<(const node & another) const {
			return !(d != another.d ? d < another.d : id < another.id);
		}
	};
	vector<node> nodes;
	int n;
	int source, sink;
	edgedata* dummy;
public:
	int result;
	Networkflow(int size, int s, int t) {
		n = size;
		source = s;
		sink = t;
		nodes.resize(n);
		dummy = new edgedata;
		init();
	}
	void init() {
		Loop(i, n) {
			nodes[i] = { i, INT_MAX, false, dummy, {} };
		}
	}
	void addedge(int s, int t, int c, int w) {
		nodes[s].edges.push_back({ s, t, c, w, dummy });
		nodes[t].edges.push_back({ t, s, 0, w * (-1) , &(nodes[s].edges.back()) });
		nodes[s].edges.back().dual_p = &(nodes[t].edges.back());
	}
	void maxflow() {
		Loop(i, n) nodes[i].edges.sort();
		result = 0;
		vector<pair<int, edgedata*>> stk;
		int a; // the node which is focused on
		int df; // how much flow in one operation
		while (1) {
			a = source;
			Loop(i, n) nodes[i].done = false;
			nodes[source].done = true;
			while (a != sink) {
				int b = -1;
				edgedata* p;
				for (auto itr = nodes[a].edges.begin(); itr != nodes[a].edges.end(); ++itr) {
					if ((*itr).capacity > 0) {
						b = (*itr).to;
						if (nodes[b].done) b = -1;
						else {
							p = &(*itr);
							stk.push_back(make_pair(a, p));
							nodes[b].done = true;
							a = b;
							break;
						}
					}
				}
				if (b == -1) {
					if (stk.empty()) break;
					a = stk.back().first;
					stk.pop_back();
				}
			}
			if (stk.empty()) break;
			df = INT_MAX;
			Loop(i, stk.size()) {
				df = min(df, (*(stk[i].second)).capacity);
			}
			while (stk.size()) {
				(*(stk.back().second)).capacity -= df;
				(*((*(stk.back().second)).dual_p)).capacity += df;
				stk.pop_back();
			}
			result += df;
		}
		return;
	}
	// if succeeding to satisfy flow then return true
	// thus if you want to gain mincostmaxflow then flow = INT_MAX and return false
	bool mincostflow(int flow) {
		Loop(i, n) nodes[i].edges.sort();
		result = 0;
		node a;
		int df; // how much flow in one operation
		int sumf = 0;
		while (1) {
			Loop(i, n) {
				nodes[i].d = INT_MAX;
				nodes[i].fromedge_p = dummy;
			}
			nodes[source].d = 0;
			Loop(k, n) {
				Loop(i, n) {
					node *a = &nodes[i];
					for (auto itr = (*a).edges.begin(); itr != (*a).edges.end(); ++itr) {
						if ((*itr).capacity == 0) continue;
						node *b = &nodes[(*itr).to];
						if ((*a).d != INT_MAX && (*a).d + (*itr).weight < (*b).d) {
							(*b).d = (*a).d + (*itr).weight;
							(*b).fromedge_p = &(*itr);
							if (k == n - 1) return false;
						}
					}
				}
			}
			if (nodes[sink].d == INT_MAX) break;
			df = INT_MAX;
			int focus = sink;
			while (focus != source) {
				df = min(df, (*(nodes[focus].fromedge_p)).capacity);
				focus = (*(nodes[focus].fromedge_p)).from;
			}
			df = min(df, flow - sumf);
			focus = sink;
			while (focus != source) {
				(*(nodes[focus].fromedge_p)).capacity -= df;
				(*((*(nodes[focus].fromedge_p)).dual_p)).capacity += df;
				focus = (*(nodes[focus].fromedge_p)).from;
			}
			sumf += df;
			result += nodes[sink].d * df;
			if (sumf == flow) return true;
		}
		return false;
	}
};

int main() {
	int v, e, f;
	cin >> v >> e >> f;
	Networkflow networkflow(v, 0, v - 1);
	Loop(i, e) {
		int s, t, c, d; cin >> s >> t >> c >> d;
		networkflow.addedge(s, t, c, d);
	}
	bool judge = networkflow.mincostflow(f);
	if (judge) cout << networkflow.result << endl;
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 3200