#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<map>
#define int long long
using namespace std;
const int M=2e4+5;
int n,m,k,fa[M],Size[M],vis[M];
struct node{
	int x,v,flag;
}s[M],c1[M],c2[M];
int maxn;
map<pair<int,int>,int>mp;
bool cmp(node a,node b){
	if(a.v==b.v)return a.x<b.x;
	return a.v<b.v;
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x);y=find(y);
	if(x==y)return ;
	if(Size[x]>Size[y])swap(x,y);
	fa[x]=y;
	Size[y]+=Size[x];
}
bool cmpcmp(node a,node b){
	int aa=a.x,bb=b.x;
	if(a.flag==2)aa+=m;
	if(b.flag==2)bb+=m;
	return aa<bb;
}
signed main(){
	scanf("%lld %lld %lld",&n,&k,&m);
	m--;
	for(int i=1;i<=m;i++)fa[i]=i,Size[i]=1;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%lld %lld",&s[i].x,&s[i].v);
		mp[make_pair(s[i].x,s[i].v)]=mp[make_pair(s[i].x,s[i].v)]=i;
		scanf("%lld %lld",&c1[i].v,&c2[i+m].v);
		c2[i].v=c1[i].v;
		c2[i].flag=1;
		c2[i+m].flag=2;
		c1[i].x=c2[i].x=c2[i+m].x=i;
	}
//	for(int i=1;i<=2*m;i++)printf("%lld: %lld\n",i,c2[i].v);
	sort(c1+1,c1+m+1,cmp);
	int cnt=0;
	for(int i=1;i<=m;i++){
		if(find(s[c1[i].x].x)!=find(s[c1[i].x].v)){
//			printf("merge(%lld,%lld)\n",s[c1[i].x].x,s[c1[i].x].v);
			merge(s[c1[i].x].x,s[c1[i].x].v);
			cnt++;vis[c1[i].x]=1;
			maxn=max(maxn,c1[i].v);
			if(cnt>=k)break;
		}
	}
	sort(c2+1,c2+2*m+1,cmp);
	cnt=k;
	for(int i=1;i<=2*m;i++){
		if(vis[c2[i].x]==0){
			int u=s[c2[i].x].x,v=s[c2[i].x].v;
//			printf("--------------%lld %lld        %lld %lld\n",u,v,find(u),find(v));
			if(find(u)!=find(v)){
				merge(u,v);
				cnt++;
				if(c2[i].flag==1)vis[c2[i].x]=1;
				else vis[c2[i].x]=2;
				maxn=max(maxn,c2[i].v);
				if(cnt>=m-2)break;
			}
		}
	}
	sort(c2+1,c2+2*m+1,cmpcmp);
	printf("%lld\n",maxn);
	for(int i=1;i<=m;i++){
		if(vis[i]!=0)printf("%lld %lld\n",i,vis[i]);
//		if(vis[i]==1)printf("%lld %lld\n",i,c2[i].v);
//		if(vis[i]==2)printf("%lld %lld\n",i,c2[i+m].v);
	}
}
/*
4 2 5 
1 2 6 5
1 3 3 1
2 3 9 4
2 4 3 1

*/