#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2e4+10;
int n,k,m,fa[N],vis[N];
struct node{
    int u,v,val,k_val,idx;
}edge[M*2];
int cnt=0,maxn=0;
pair<int,int> ans[N];
bool cmp(node a,node b){
    return a.val<b.val;
}
inline int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
inline bool merge(int a,int b){
    int t1=find(a),t2=find(b);
    if(t1==t2) return false;
    fa[t1]=t2;
    return true;
}
signed main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    int tot=0;
    for(int i=1,a,b,c1,c2;i<=m-1;i++){
        cin>>a>>b>>c1>>c2;
        edge[++tot]={a,b,c1,1,i};
        edge[++tot]={a,b,c2,0,i};
    }
    sort(edge+1,edge+1+tot,cmp);
    int tot1=0;
    for(int i=1;i<=tot;i++){
        if(tot1>=k) break;
        if(edge[i].k_val){
            int u=edge[i].u,v=edge[i].v,idx=edge[i].idx;
            if(merge(u,v) && !vis[idx]){
                ans[++cnt]={idx,1};
                maxn=max(maxn,edge[i].val);
                tot1++;
                vis[idx]=1;
            }
        }
    }
    for(int i=1;i<=tot;i++){
        int u=edge[i].u,v=edge[i].v,idx=edge[i].idx;
        int type=(edge[i].k_val==1?1:2);
        if(merge(u,v) && !vis[idx]){
            vis[idx]=1;
            ans[++cnt]={idx,type};
            maxn=max(maxn,edge[i].val);
        }
        if(cnt==n-1){
            cout<<maxn<<'\n';
            sort(ans+1,ans+cnt+1);
            for(int i=1;i<=cnt;i++) cout<<ans[i].first<<' '<<ans[i].second<<'\n';
            return 0;
        }
    }
	return 0;
}