#include <bits/stdc++.h>
using namespace std;
int v, e;
vector<pair<int, int> > adj[110], revadj[110];
int capacity[1010], cost[1010], cost2[1010], rcost2[1010], flowingthrough[1010], dis[110], pre[110], preedge[110], endofedge[1010], startofedge[1010];
int potential[110];
void bellmanford()
{
	fill_n(dis, v, 1e9);
	dis[0] = 0;
	for (int f = 0; f < v; f++)
	{
		for (int i = 0; i < v; i++)
		{
			for (auto e : adj[i])
			{
				if (flowingthrough[e.second] != capacity[e.second])
				{
					if (dis[e.first] > dis[i] + cost[e.second])
					{
						dis[e.first] = dis[i] + cost[e.second];
						pre[e.first] = i;
						preedge[e.first] = e.second;
					}
				}
			}
			for (auto e : revadj[i])
			{
				if (flowingthrough[e.second])
				{
					if (dis[e.first] > dis[i] - cost[e.second])
					{
						dis[e.first] = dis[i] - cost[e.second];
						pre[e.first] = i;
						preedge[e.first] = e.second;
					}
				}
			}
		}
	}
}
void dijkstras()
{
	fill_n(dis, v, 1e9);
	dis[0] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.emplace(0, 0);
	while (pq.size())
	{
		int i = pq.top().second;
		int d = pq.top().first;
		pq.pop();
		if (d != dis[i]) continue;
		for (auto e : adj[i])
		{
			if (flowingthrough[e.second] != capacity[e.second])
			{
				assert(cost2[e.second] >= 0);
				if (dis[e.first] > dis[i] + cost2[e.second])
				{
					dis[e.first] = dis[i] + cost2[e.second];
					pre[e.first] = i;
					preedge[e.first] = e.second;
					pq.emplace(dis[e.first], e.first);
				}
			}
		}
		for (auto e : revadj[i])
		{
			if (flowingthrough[e.second])
			{
				assert(rcost2[e.second] >= 0);
				if (dis[e.first] > dis[i] + rcost2[e.second])
				{
					dis[e.first] = dis[i] + rcost2[e.second];
					pre[e.first] = i;
					preedge[e.first] = e.second;
					pq.emplace(dis[e.first], e.first);
				}
			}
		} 
	}
}
void adjustweights()
{
	for (int i = 0; i < v; i++) potential[i] += dis[i];
	for (int i = 0; i < e; i++)
	{
		cost2[i] = cost[i] + potential[startofedge[i]] - potential[endofedge[i]];
		rcost2[i] = -cost[i] - potential[startofedge[i]] + potential[endofedge[i]];

	//	printf("%d %d - %d %d (%d, %d) initial %d\n", cost2[i], rcost2[i], potential[startofedge[i]], potential[endofedge[i]], startofedge[i], endofedge[i], cost[i]);
	//	assert(cost2[i] >=0 );
	//	assert(rcost2[i] >=0 );
	}
}
pair<int, int> mincostmaxflow()
{
	int ans = 0;
	int totalcost = 0;
	bellmanford();
	while (1)
	{
		adjustweights();
		dijkstras();
		if (dis[v-1] == 1e9) break;
		ans++;
		// Augment path
		int a = v-1;
		while (a)
		{
	//		printf("%d ", a);
			int e = preedge[a];
			if (endofedge[e] == a) flowingthrough[e]++, totalcost += cost[e];
			else flowingthrough[e]--, totalcost -= cost[e];
			a = pre[a];
		}
	//	printf("%d\n", a);
	}
	return { ans, totalcost };
}
int f;
int main()
{
	scanf("%d%d%d", &v, &e, &f);
	for (int i = 0; i < e; i++)
	{
		int a, b;
		scanf("%d%d%d%d", &a, &b, &capacity[i], &cost[i]);
		cost2[i] = cost[i];
		assert(a != b);
		endofedge[i] = b;
		startofedge[i] = a;
		adj[a].emplace_back(b, i);
		revadj[b].emplace_back(a, i);
	}
	adj[v-1].emplace_back(v, e);
	cost[e] = 0;
	startofedge[e] = v-1;
	endofedge[e] = v;
	capacity[e++] = f;
	v++;
	auto ans = mincostmaxflow();
//	printf("%d %d\n", ans.first, ans.second);
	if (ans.first != f) printf("-1\n");
	else printf("%d\n", ans.second);
}


Measured memory_bytes: 3284