#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u, v, w;
    int no, first;
};
edge first[20000], second[20000];
vector<list<int> > graph;
vector<edge> answers;
int fa[20000];
int findx(int x){
    if(fa[x] == x) return x;
    return fa[x] = findx(fa[x]);
}
int main(){
    int n, k, m, ans = 0, tot = 0;
    scanf("%d %d %d", &n, &k, &m);
    for(int i = 0; i <= n; i++) fa[i] = i;
    graph.resize(n + 1);
    for(int i = 0, a, b, c1, c2; i < m - 1; i++){
        scanf("%d %d %d %d", &a, &b, &c1, &c2);
        first[i] = (edge){a, b, c1, i + 1, 1}, second[i] = (edge){a, b, c2, i + 1, 2};
    }
    sort(first, first + m - 1, [](edge a, edge b)->bool{
        return a.w < b.w;
    });
    sort(second, second + m - 1, [](edge a, edge b)->bool{
        return a.w < b.w;
    });
    for(int i = 0; i < m - 1 && tot != k + 1; i++){
        if(findx(first[i].u) == findx(first[i].v)){
            continue;
        }
        graph[first[i].u].push_back(first[i].v);
        graph[first[i].v].push_back(first[i].u);
        ans = max(ans, first[i].w), tot++;
        fa[findx(first[i].u)] = findx(first[i].v);
        answers.push_back(first[i]);
    }
    for(int i = 0; i < m - 1 && tot != n; i++){
        if(findx(second[i].u) == findx(second[i].v)){
            continue;
        }
        graph[second[i].u].push_back(second[i].v);
        graph[second[i].v].push_back(second[i].u);
        ans = max(ans, second[i].w), tot++;
        fa[findx(second[i].u)] = findx(second[i].v);
        answers.push_back(second[i]);
    }
    sort(answers.begin(), answers.end(), [](edge a, edge b)->bool{
        return a.no < b.no;
    });
    printf("%d\n", ans);
    for(int i = 0; i < n - 1; i++){
        printf("%d %d\n", answers[i].no, answers[i].first);
    }
    return 0;
}