code:

#include<bits/stdc++.h>
using namespace std;
struct node{
	int from,to;
	int dis1,dis2;
	int num;
}e[20005];
struct road{
	int num;
	int lv;
}ans[20005];
int n,k,m,maxn,cnt;
int fa[20005];
bool used[20005];
void init(){
	for(int i=1;i<=n;i++)
		fa[i]=i;
}
bool cmp1(node a,node b){
	return a.dis1<b.dis1;
}
bool cmp2(node a,node b){
	return a.dis2<b.dis2;
}
bool cmp3(road a,road b){
	return a.num<b.num;
}
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
int main()
{
	cin>>n>>k>>m;
	init();
	for(int i=1;i<=m-1;i++){
		cin>>e[i].from>>e[i].to>>e[i].dis1>>e[i].dis2;
		e[i].num=i;
	}
	sort(e+1,e+m,cmp1);
	int r=0;
	for(int i=1;i<=m-1;i++){
		if(r>=k) break;
		int u=find(e[i].from),v=find(e[i].to);
		if(u!=v){
			fa[u]=v;
			r++;
			maxn=max(maxn,e[i].dis1);
			used[e[i].num]=true;
			ans[++cnt].num=e[i].num;
			ans[cnt].lv=1;
		}
	}
	init();
	sort(e+1,e+m,cmp2);
	for(int i=1;i<=m-1;i++){
		if(r>=n-1) break;
		int u=find(e[i].from),v=find(e[i].to);
		if(u!=v&&used[e[i].num]==false){
			fa[u]=v;
			r++;
			maxn=max(maxn,e[i].dis2);
			ans[++cnt].num=e[i].num;
			ans[cnt].lv=2;
			//used[e[i].num]=true;
		}
	}
	sort(ans+1,ans+1+cnt,cmp3);
	cout<<maxn<<endl;
	for(int i=1;i<=cnt;i++){
		cout<<ans[i].num<<' '<<ans[i].lv<<endl;
	}
	return 0;
}