#include <algorithm>

#include <cstdio>

#define N 20005

using namespace std;

struct Edge

{

    int x,y,z,id;

    bool operator<(Edge a)const

    {

        return z<a.z;

    }

}e1[N],e2[N];

struct node

{

    int a,b;

    bool operator<(node x)const

    {

        return a<x.a;

    }

}ans[N];

int n,k,m,siz,fa[N];

int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);}

bool check(int x)

{

    for(int i=;i<=n;++i) fa[i]=i;

    int num=;

    for(int i=;i<=m;++i)

    {

        if(e1[i].z>x) continue;

        int fx=find_(e1[i].x),fy=find_(e1[i].y);

        if(fx!=fy)

        {

            num++;

            fa[fy]=fx;

        }

    }

    if(num<k) return false;

    for(int i=;i<=m;++i)

    {

        if(e2[i].z>x) continue;

        int fx=find_(e2[i].x),fy=find_(e2[i].y);

        if(fx!=fy)

        {

            fa[fy]=fx;

            num++;

        }

    }

    if(num==n-) return true;

    return false;

}

void get(int x)

{

    for(int i=;i<=n;++i) fa[i]=i;

    for(int i=;i<=m;++i)

    {

        if(e1[i].z>x) continue;

        int fx=find_(e1[i].x),fy=find_(e1[i].y);

        if(fx!=fy)

        {

            siz++;

            fa[fy]=fx;

            ans[siz].a=e1[i].id;

            ans[siz].b=;

        }

    }

    for(int i=;i<=m;++i)

    {

        if(e2[i].z>x) continue;

        int fx=find_(e2[i].x),fy=find_(e2[i].y);

        if(fx!=fy)

        {

            siz++;

            fa[fy]=fx;

            ans[siz].a=e2[i].id;

            ans[siz].b=;

        }

    }

}

int main(int argc,char *argv[])

{

    scanf("%d%d%d",&n,&k,&m);

    int l=,r=,anss;

    for(int u,v,w1,w2,i=;i<=m;++i)

    {

        scanf("%d%d%d%d",&u,&v,&w1,&w2);

        e1[i]=(Edge){u,v,w1,i};

        e2[i]=(Edge){u,v,w2,i};

        r=max(r,w1);

    }

    sort(e1+,e1+m);

    sort(e2+,e2+m);

    for(int mid;l<=r;)

    {

        mid=(l+r)>>;

        if(check(mid))

         anss=mid,r=mid-;

        else l=mid+;

    }

    printf("%d\n",anss);

    get(anss);

    sort(ans+,ans++siz);

    for(int i=;i<=siz;++i) printf("%d %d\n",ans[i].a,ans[i].b);

    return ;

}