#include <bits/stdc++.h>
using namespace std;
const int MAXM = 20000;
const int MAXN = 10000;
int n, k, m;
struct Edge
{
    int u, v, p1, p2, id;
};
Edge e[MAXM + 5];
// 存最大花费及方案
int ans;
vector<pair<int, int>> plan;
// 按 p1 排序
bool cmp1(Edge e1, Edge e2)
{
    return e1.p1 < e2.p1;
}
// 按 p2 排序
bool cmp2(Edge e1, Edge e2)
{
    return e1.p2 < e2.p2;
}
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].p1 >> e[i].p2;
        e[i].id = i;
    }
    // 并查集初始化
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    // 记录答案
    ans = 0;
    // 先建 k 条一级公路，挑小的建
    sort(e + 1, e + m + 1, cmp1);
    for (int i = 1, cnt = 0; i <= m; i++)
    {
        int faU = findFa(e[i].u);
        int faV = findFa(e[i].v);
        if (faU != faV)
        {
            ans = max(ans, e[i].p1);
            fa[faU] = faV;
            plan.push_back({e[i].id, 1});
            cnt++;
            if (cnt == k)
                break;
        }
    }
    // 然后剩下的用二级公路补
    sort(e + 1, e + m + 1, cmp2);
    for (int i = 1; i <= m; i++)
    {
        int faU = findFa(e[i].u);
        int faV = findFa(e[i].v);
        if (faU != faV)
        {
            ans = max(ans, e[i].p2);
            fa[faU] = faV;
            plan.push_back({e[i].id, 2});
        }
    }
    // 输出
    cout << ans << "\n";
    sort(plan.begin(), plan.end());
    for (int i = 0; i < plan.size(); i++)
        cout << plan[i].first << " " << plan[i].second << "\n";
    return 0;
}