#include <bits/stdc++.h>
using namespace std;
int n,k,m;
int tp[20010];
int a[20010],b[20010],c1[20010],c2[20010];
int fa[20010];
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool ch(int mid)
{
	int cnt = 0,tot = 0;
	for (int i = 1;i <= n;i++)
	{
		fa[i] = i;
	}
	for (int i = 1;i <= m;i++)
	{
		tp[i] = 0;
	}
	for (int i = 1,x,y;i <= m;i++)
	{
		if ((x = find(a[i])) != (y = find(b[i])) && c1[i] <= mid)
			tp[i] = 1,cnt++,fa[x] = y,tot++;
	}
	for (int i = 1,x,y;i <= m;i++)
	{
		if ((x = find(a[i])) != (y = find(b[i])) && c2[i] <= mid)
			tp[i] = 2,fa[x] = y,tot++;
	}
	return cnt >= k && tot == n - 1;
}
int main()
{
	cin >> n >> k >> m;
	m--;
	for (int i = 1;i <= m;i++)
	{
		cin >> a[i] >> b[i] >> c1[i] >> c2[i];
	}
	int l = 1,r = 30000;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (ch(mid)) r = mid-1;
		else l = mid+1;
	}
	cout << l << '\n';
	for (int i = 1;i <= m;i++)
	{
		if (tp[i])
		{
			cout << i << ' ' << tp[i] << endl;
		}
	}
	return 0;
}