//rt
#include<iostream>
#include<cstdio>
#include<algorithm> 
using namespace std;
struct node
{
    int fr,to,dis1,dis2,net,use;
}edg[100011];
struct node3
{
    int kind,use;
}edgg[100011];
int cnt,pre[20001],n,m,k,sidede;
int in(int x,int y,int cost1,int cost2)
{
    cnt++;
    edg[cnt].fr=x;
    edg[cnt].to=y;
    edg[cnt].dis1=cost1;
    edg[cnt].dis2=cost2;
    edg[cnt].net=cnt;
}
int find(int x)
{    
    int x1=x;
    while(pre[x]!=x)
    x=pre[x];
    int t;
    while(x1!=x)
    {
        t=pre[x1];
        pre[x1]=x;
        x1=t;
    }
    return x;
}
int cmp1(const node &a,const node &b)
{
    return a.dis1<b.dis1;
}
int cmp2(const node &a,const node &b)
{
    return a.dis2<b.dis2;
}
int mix(int a,int b)
{
    if(find(a)==find(b))    return 0;
    pre[find(a)]=find(b);
    return 1;
}
bool can(int x)
{
    for(int i=1;i<=cnt;++i)
    edg[i].use=0;
    int ans=x; 
    int kside=0,side=0;
    for(int i=1;i<=n;++i)
    pre[i]=i;
    sort(edg+1,edg+cnt+1,cmp1);
    for(int i=1;i<=cnt;++i)
    if(edg[i].dis1<=ans && mix(edg[i].to,edg[i].fr))
    {
        kside++,side++;
    }
    sort(edg+1,edg+cnt+1,cmp2);
    for(int i=1;i<=cnt;++i)
    if(edg[i].dis2<=ans && mix(edg[i].to,edg[i].fr))
    {    
        side++;
    }
    if(side>=n-1 && kside>=k)    
    {
        sidede=side;
        return 1;
    }
    return 0;
}
int dfs(int l,int r)
{
    if(r==l)    return r;
    int mid=(l+r>>1);
    if(can(mid))    dfs(l,mid);
    else            dfs(mid+1,r);    
}
int cmp3(const node3 &a,const node3 &b)
{
    return a.use<b.use;
}
int main()
{
    cin>>n>>k>>m;//zhi shao k tiao
    for(int i=1,x,y,c1,c2;i<=m;++i)
    scanf("%d%d%d%d",&x,&y,&c1,&c2),in(x,y,c1,c2);
    int anss=dfs(1,30001);
    cout<<anss<<endl;
    for(int i=1;i<=n;++i)
    pre[i]=i;
    int t=0;
    for(int i=1;i<=cnt;++i)//得到答案后重新寻找路径 
    {
        int too=edg[i].to;
        int from=edg[i].fr;
        if(edg[i].dis1<=anss)
        if(mix(too,from))
        {
            edgg[++t].kind=1,edgg[t].use=edg[i].net;
        }
    }
    for(int i=1;i<=cnt;++i)//得到答案后重新寻找路径 
    {
        int too=edg[i].to;
        int from=edg[i].fr;
        if(edg[i].dis2<=anss)
        if(mix(too,from))
        {
            edgg[++t].kind=2,edgg[t].use=edg[i].net;
        }
    }
    sort(edgg+1,edgg+sidede+1,cmp3);
    for(int i=1;i<=sidede;++i)
    cout<<edgg[i].use<<" "<<edgg[i].kind<<endl;
}