#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5;
int k[2];
struct Edge{
	int s,t,c,col;
	void print(){
		cout<<s<<" "<<t<<" "<<c<<" "<<col<<'\n';
	}
}eg[MAXN*2];
int V,E,need;
int fa[MAXN*2];
int find_fa(int x){
	if(fa[x]==x)return x;
	return fa[x]=find_fa(fa[x]);
}
bool cmp(Edge x,Edge y){
	if(x.c+k[x.col]==y.c+k[y.col])return x.col<y.col;
	return x.c+k[x.col]<y.c+k[y.col];
}
bool check(int x){
	int res=0,cnt=0;
	k[0]=x;
	//cout<<x<<'\n';
	for(int i=0;i<=V;i++)fa[i]=i;
	sort(eg+1,eg+E+1,cmp);
	for(int i=1;i<=E&&cnt!=V-1;i++){
		//eg[i].print();
		int f1=find_fa(eg[i].s);
		int f2=find_fa(eg[i].t);
		if(f1==f2)continue;
		cnt++;
		fa[f1]=f2;
		if(!eg[i].col)res++;
		//cout<<res<<'\n';
	}
	return res>=need;
}
int main(){
	cin>>V>>E>>need;
	for(int i=1;i<=E;i++){
		int s,t,c,col;
		cin>>s>>t>>c>>col;
		eg[i]={s,t,c,col};
	}
	int l=-100,r=100;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
		cout<<mid<<'\n';
	}
	cout<<l<<'\n';
	k[0]=l;
	int ans=0,cnt=0;
	for(int i=0;i<=V;i++)fa[i]=i;
	sort(eg+1,eg+E+1,cmp);
	for(int i=1;i<=E&&cnt!=V-1;i++){
		eg[i].print();
		int f1=find_fa(eg[i].s);
		int f2=find_fa(eg[i].t);
		if(f1==f2)continue;
		cnt++;
		fa[f1]=f2;
		ans+=eg[i].c;
		cout<<ans<<'\n';
	}
	cout<<ans<<'\n';
	return 0;
}