#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,fa[500001],cnt,ans,x,y;
struct ac{
	int x,y,z1,z2,id;
}a[200005];
struct acc{
	int x,y;
}b[10001];
int zhao(int x){
	if(fa[x]!=x) fa[x]=zhao(fa[x]);
	return fa[x];
}
bool cmp(ac a,ac b){
	if(a.z1!=b.z1){
		return a.z1<b.z1;
	}else{
		return a.z2<b.z2;
	}
}
bool cmpp(acc a,acc b){
	return a.x<b.x;
}
int main(){
	cin>>n>>x>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z1>>a[i].z2;
		a[i].id=i;
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		int xx=zhao(a[i].x),yy=zhao(a[i].y);
		if(xx==yy){
			continue;
		}
		fa[yy]=xx;
		cnt++;
		ans=max(ans,a[i].z1);
		b[cnt].x=a[i].id;
		b[cnt].y=1;
		if(cnt==x){
			break;
		}
	}
	for(int i=1;i<=m;i++){
		int xx=zhao(a[i].x),yy=zhao(a[i].y);
		if(xx==yy){
			continue;
		}
		fa[yy]=xx;
		cnt++;
		if(a[i].z2>a[i].z1){
			ans=max(ans,a[i].z1);
			b[cnt].y=1;
		}else{
			ans=max(ans,a[i].z2);
			b[cnt].y=2;
		}
		b[cnt].x=a[i].id;
		if(cnt==n-1){
			break;
		}
	}
	cout<<ans<<endl;
	sort(b+1,b+1+cnt,cmpp);
	for(int i=1;i<n;i++){
		cout<<b[i].x<<" "<<b[i].y<<endl;
	}
	return 0;
}