#include <bits/stdc++.h>
using namespace std;
const int max_=3e4+5;
int n,k,m,fa[max_];
struct node{
    int x,y,s,t,pos;
}a[max_];
bool use[max_];
int root(int x){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=root(fa[x]);
}
bool cmp(node x,node y){
    return x.s<y.s;
}
bool comp(node x,node y){
    return x.t<y.t;
}
vector<pair<int,int>>rp;
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); 
    cin>>n>>k>>m;
    for(int i=1;i<m;i++){
        cin>>a[i].x>>a[i].y>>a[i].s>>a[i].t;
        a[i].pos=i;
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    sort(a+1,a+m,cmp);
    int cnt=0,ans=0;
    for(int i=1;i<m&&cnt<k;i++){
        int rx=root(a[i].x),ry=root(a[i].y);
        if(rx^ry&&!use[a[i].pos]){
            fa[rx]=ry;
            ans=max(ans,a[i].s);
            cnt++;
            rp.push_back(make_pair(a[i].pos,1));
            use[a[i].pos]=1;
        }
    }
    sort(a+1,a+m,comp);
    for(int i=1;i<m&&cnt<n-1;i++){
        int rx=root(a[i].x),ry=root(a[i].y);
        if(rx^ry&&!use[a[i].pos]){
            fa[rx]=ry;
            ans=max(ans,a[i].t);
            cnt++;
            rp.push_back(make_pair(a[i].pos,2));
            use[a[i].pos]=1;
        }
    }
    cout<<ans<<'\n';
    sort(rp.begin(),rp.end());
    for(auto i:rp){
        cout<<i.first<<' '<<i.second<<'\n';
    }
    return 0;
}