#include<bits/stdc++.h>
#define re register
const int maxn = 1e5 + 10, maxm = 2e5 + 10;
using namespace std;
int n, k, m, ans[maxm], f[maxn], maxx = INT_MIN, best[maxn], cnt;
bool vis[maxm];
struct nd {
	int a, b, c1, c2;
} e[maxm];
int find(int u) {
	return u == f[u] ? u : find(f[u]);
}
void hb(int u, int v) {
	f[find(u)] = find(v);
}
bool btr(int u, int v) {
	if (v == 0) return 1;
	if (cnt < k) {
		if (e[u].c1 != e[v].c1)
			return e[u].c1 <= e[v].c1;
	}
	return e[u].c2 <= e[v].c2;
	if (e[u].c2 != e[v].c2) {
		return u < v;
	}
}
void boruvka() {
	bool status = true;
	while (status) {
		status = false;
		memset(best, 0, sizeof best);
		for (re int i = 1; i <= m; ++i) {
			if (!vis[i]) {
				int uu = find(e[i].a), vv = find(e[i].b);
				if (uu == vv) {
					continue;
				}
				if (btr(i, best[uu])) {
					best[uu] = i;
				}
				if (btr(i, best[vv])) {
					best[vv] = i;
				}
			}
		}
		for (re int i = 1; i <= n; ++i) {
			if (best[i] && !vis[best[i]]) {
				status = true;
				cnt++;
				vis[best[i]] = 1;
				hb(e[best[i]].a, e[best[i]].b);
				if (cnt <= k) {
					maxx = max(maxx, e[best[i]].c1);
					ans[best[i]] = 1;
				} else {
					maxx = max(maxx, e[best[i]].c2);
					ans[best[i]] = 2;
				}
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &k, &m);
	for (re int i = 1; i <= m - 1; ++i) {
		scanf("%d%d%d%d", &e[i].a, &e[i].b, &e[i].c1, &e[i].c2);
	}
	for (re int i = 1; i <= n; ++i) {
		f[i] = i;
	}
	boruvka();
	printf("%d\n", maxx);
	for (int i = 1; i <= m; ++i) {
		if (ans[i] == 0) {
			continue;
		}
		printf("%d %d\n", i, ans[i]);
	}
	return 0;
}