/**************************************************************
Problem: 1834
User: OceanEYe
Language: C++
Result: Accepted
Time:56 ms
Memory:1948 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#define p(x) ('0'<=x&&x<='9')
#define INF 100000000
char cc; int C;
template <class T>
void read(T &x)
{
cc=getchar(); C=1; x=0;
while(!p(cc))
{
if(cc=='-') C=-1;
cc=getchar();
}
while(p(cc)) x=x*10+cc-48,cc=getchar();
x*=C;
}
template <class T>
void MN(T &x,T y) { x>y?x=y:x=x; }
using namespace std;
#define N 1005
#define E 10010
struct Tedge
{
int from,to,cap,flow;
int val;
}edge[E<<2];
#define TO edge[i].to
#define VAL edge[i].val
#define SIZ (edge[i].cap-edge[i].flow)
#define CAP edge[i].cap
int fst[N],NXT[E<<2],e_tot;
void add_e(int _,int __,int ___,int ____)
{
edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].from=_; edge[e_tot].val=____;
NXT[e_tot]=fst[_]; fst[_]=e_tot++;
edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; edge[e_tot].from=__; edge[e_tot].val=-____;
NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}
int S,T;
struct rec
{
int a,b,c,d;
rec(int _,int __,int ___,int ____): a(_),b(__),c(___),d(____) {}
};
vector <rec> R;
int n,m,k;
void init1()
{
read(n); read(m); read(k);
S=1; T=n;
int _,__,___,____;
memset(fst,-1,sizeof(fst));
for(int i=1;i<=m;i++)
{
read(_); read(__); read(___); read(____);
add_e(_,__,___,0);
R.push_back(rec(_,__,___,____));
}
}
//
bool vis[N];
int d[N],cnt[N],p[N],pre[N],ans;
int Augment()
{
int r=T,c=INF,i;
while(r!=S)
{
i=pre[r];
MN(c,CAP-SIZ);
r=TO;
}
r=T;
while(r!=S)
{
i=pre[r];
edge[i].flow-=c; edge[i^1].flow+=c;
r=TO;
}
return c;
}
void ISAP()
{
int node=S,c;
for(int i=1;i<=n;i++) p[i]=fst[i];
bool flag;
while(d[S]<=n)
{
if(node==T)
{
ans+=Augment();
node=S;
}
//solve
flag=false;
for(int i=p[node];~i;i=NXT[i])
{
if(d[TO]!=d[node]-1||SIZ==0) continue;
p[node]=i;
pre[TO]=i^1;
node=TO;
flag=true;
break;
}
if(flag) continue;
c=n+10;
for(int i=fst[node];~i;i=NXT[i])
{
if(!SIZ) continue;
MN(c,d[TO]+1);
}
if(--cnt[d[node]]==0)
{
printf("%d ",ans);
return;
}
cnt[d[node]=c]++;
p[node]=fst[node];
if(node!=S)node=edge[pre[node]].to;
//retreat
}
printf("%d ",ans);
}
queue<int> Q;
void bfs()
{
int x;
memset(vis,0,sizeof(vis));
d[T]=1; Q.push(T); vis[T]^=1;
while(!Q.empty())
{
x=Q.front(); Q.pop();
cnt[d[x]]++;
for(int i=fst[x];~i;i=NXT[i])
{
if(vis[TO]||SIZ) continue;
d[TO]=d[x]+1;
Q.push(TO);
vis[TO]^=1;
}
}
}
//
int dis[N],cost;
void init2()
{
int _,__,___,____;
for(int i=0;i<m;i++)
{
_=R[i].a;
__=R[i].b;
____=R[i].d;
add_e(_,__,INF,____);
}
}
int Augment2()
{
int r=T,c=0,i;
while(r!=S)
{
i=pre[r];
edge[i].flow--; edge[i^1].flow++;
c+=edge[i^1].val;
r=TO;
}
return c;
}
void SPFA()
{
memset(dis,0x7f,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[S]=0; Q.push(S); vis[S]=true;
int x,i;
while(!Q.empty())
{
x=Q.front(); Q.pop(); vis[x]=false;
for(i=fst[x];~i;i=NXT[i])
{
if(!SIZ) continue;
if(dis[TO]<=dis[x]+VAL) continue;
dis[TO]=dis[x]+VAL;
pre[TO]=i^1;
if(vis[TO]) continue;
vis[TO]=true;
Q.push(TO);
}
}
cost+=Augment2();
}
//
int main()
{
init1();
bfs();
ISAP();
init2();
for(int i=1;i<=k;i++) SPFA();
printf("%d\n",cost);
return 0;
}