个人猜测是选了太多边。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int minn=INT_MIN;
long long sum;
bool book[20010];
int f[10010];
struct road{
	int u,v,w1,w2,num;
}rd[20010];
struct ptbr{
	int bh,dj;
}ans[20010];
int find(int x)
{
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
bool cmp1(road x,road y)
{
	return x.w1<y.w1;
}
bool cmp2(road x,road y)
{
	return x.w2<y.w2;
}
bool cmp3(ptbr x,ptbr y)
{
	return x.bh<y.bh;
}
int main()
{
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<m;i++)
	{
		int a,b,c1,c2;
		scanf("%d%d%d%d",&a,&b,&c1,&c2);
		rd[i].u=a,rd[i].v=b,rd[i].w1=c1,rd[i].w2=c2,rd[i].num=i;
	}
	sort(rd+1,rd+n+1,cmp1);
	int hg=0,flag=0;
	for(int i=1;i<=m-1;i++)
	{
		int fu=find(rd[i].u);
		int fv=find(rd[i].v);
		if(fu!=fv)
		{
			f[fu]=fv;
			book[rd[i].num]=true;
			hg++;
			flag++;
			minn=max(minn,rd[i].w1);
			ans[flag].bh=rd[i].num;
			ans[flag].dj=1;
			if(hg==k)break;
		}
	}
	
	sort(rd+1,rd+n+1,cmp2);
	for(int i=1;i<=m-1;i++)
	{
		if(book[rd[i].num])continue;
		int fu=find(rd[i].u);
		int fv=find(rd[i].v);
		if(fu!=fv)
		{
			f[fu]=fv;
			book[rd[i].num]=true;
			flag++;
			minn=max(minn,rd[i].w2);
			ans[flag].bh=rd[i].num;
			ans[flag].dj=2;
			if(flag==n-1)break;
		}
	}
	sort(ans+1,ans+flag+1,cmp3);
	cout<<minn<<endl;
	for(int i=1;i<=flag;i++)
	printf("%d %d\n",ans[i].bh,ans[i].dj);
}