#include<bits/stdc++.h>
#define jntm mid=(l+r)>>1
using namespace std;
struct node{
	int u,v,w,c;
}b[500001]; 
int f[500001],siz[500001],n,m,k,mid;
bool cmp(node a,node b){
	return a.w<b.w;
} 
int find(int x){return(f[x]==x?x:f[x]=find(f[x]));}
pair<int,int> SST(){
	for(int i=1;i<=n+10;++i)f[i]=i,siz[i]=1;
	int ans=0,i=1,jbcj=0;
	sort(b+1,b+1+m,cmp);
	int kun=0;
	while(jbcj<n-1){
//		if(i>m)return-114514;
		int x=find(b[i].u),y=find(b[i].v);
		if(siz[x]>siz[y])swap(x,y);
		if(x!=y)f[x]=y,ans+=b[i].w,++jbcj,siz[y]+=siz[x],kun+=(b[i].c);
		++i;
	}
	return make_pair(ans,kun);
}
int main(){
	freopen("P2619_11.in","r",stdin);
	cin>>n>>m>>k;
	for(int i=1;i<=m;++i){
		cin>>b[i].u>>b[i].v>>b[i].w>>b[i].c;
		b[i].c=!b[i].c,b[i].u++,++b[i].v;
	}
	int l=-111,r=111;
	pair<int,int>ans;
	int sum=0;
	while(l<=r){
		cout<<l<<' '<<r<<'\n';
		jntm;
		for(int i=1;i<=m;++i){
			b[i].w+=mid*b[i].c;
		}
		ans=SST();
		if(ans.second<k)r=mid-1; 
		else if(ans.second>=k)(cout<<ans.first-mid*k<<'\n'),l=mid+1,sum=(ans.first-mid*k);
		
		for(int i=1;i<=m;++i){
			b[i].w-=mid*b[i].c;
		}
	}
	cout<<sum;
	return 0;
}