思路是先走二级公路，在选了的路上走最小的一级公路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10;
const int M = 2e4 + 10;
int n, kk, m;
int fa[N], ans;
int road[N], rd[N], cnt, g;

struct node{
	int x, y, c1, tt;
}kru[M];

bool cmp(node a, node b){
	return a.c1 < b.c1;
}

struct Node{
	int idx, c2;
}k[M];

bool Cmp(Node a, Node b){
	return a.c2 < b.c2 ;
}

inline int get(int a){
	if(a == fa[a]) return a;
	else return fa[a] = get(fa[a]);
}

int main(){
	scanf("%d%d%d", &n, &kk, &m);
	for(int i = 1; i <= n ; ++ i){
		road[i] = 2;
	}
	for(int i = 1; i < m; ++ i){
		int a, b, c, cc;
		scanf("%d%d%d%d", &a, &b, &c, &cc);
		kru[i].x = a; kru[i].y = b; kru[i].c1 = c; kru[i].tt = i; k[i].c2 = cc; k[i].idx = i;
	}
	sort(kru + 1, kru + m, cmp);
	sort(k + 1, k + m , Cmp);
	
	for(int i = 1; i <= n; ++ i) fa[i] = i;
	for(int i = 1; i < n; ++ i){
		int x = get(kru[i].x);
		int y = get(kru[i].y);
		if(x == y) continue;
		rd[ ++ cnt] = kru[i].tt;
		fa[x] = y;
		ans = max(ans, kru[i].c1);
	}
	sort(rd + 1, rd + cnt + 1);
	for(int i = 1; i <= n; ++ i){
		if(rd[i]){
			ans = max(ans, k[i].c2);
			road[k[i].idx] = 1;
			g ++;
			if(g == kk) break;
		}
	}
	printf("%d\n", ans);
	for(int i = 1; i < n; ++ i){
		printf("%d %d\n", rd[i], road[rd[i]]);
	}
	return 0;
}