#include <iostream>
#include <algorithm>
using namespace std;


struct edge{
	int start,stop,len,index;
};


bool cmp(edge a,edge b){
	return a.len<b.len;
}


bool cmp2(edge a,edge b){
	return a.index<b.index;
}


int find(int x,int f[]){
	if(f[x] == x)
		return x;
	return f[x]=find(f[x],f);
}


int main(){
	int ansn=0;
	int n,k,m;
	cin>>n>>k>>m;
	m--;
	edge e1[m],e2[m];
	edge ea[n-1];
	int index=0;
	for(int i=0;i<m;i++){
		int a,b,c1,c2;
		cin>>a>>b>>c1>>c2;
		a--;
		b--;
		e1[i] = {a,b,c1,i};
		e2[i] = {a,b,c2,i};
	}
	
	sort(e1,e1+m,cmp);
	sort(e2,e2+m,cmp);
	
	
	int f[n];
	for(int i=0;i<n;i++)
		f[i] = i;
	
	int p=0;
	for(int i=0;i<k;i++){
		while(find(e1[p].start,f) == find(e1[p].stop,f)) p++;
		f[find(e1[p].start,f)] = find(e1[p].stop,f);
		ansn = ansn>e1[p].len?ansn:e1[p].len;
		ea[index].len = 1;
		ea[index].index = e1[p].index;
		index++;
	}
	
//	for(int i=0;i<n;i++)
//		cout<<f[i]<<" ";
//	cout<<endl;
	
	p = 0;
	while(index <= n-2){
		while(find(e2[p].start,f) == find(e2[p].stop,f)) p++;
//		cout<<p<<endl;
		f[find(e2[p].start,f)] = find(e2[p].stop,f);
		ansn = ansn>e2[p].len?ansn:e2[p].len;
		ea[index].len = 2;
		ea[index].index = e2[p].index;
		index++;
	}
	
	sort(ea,ea+n-1,cmp2);
	cout<<ansn<<endl;
	for(int i=0;i<n-1;i++){
		cout<<ea[i].index+1<<" "<<ea[i].len<<endl;
	}
	return 0;
}