#include<bits/stdc++.h>
using namespace std;
ifstream f("elicoptere.in");
ofstream g("elicoptere.out");
struct triunghi
{
    int x1,y1;
    int x2,y2;
    int x3,y3;
};
triunghi tri[110];
int t[100010],p,n,k;
float v[110][110],cost;
int nr,nr1,viz[100010];
pair<float, pair<int, int> > v1[110];
vector<pair<int, int> > sol;
float distv(float a1, float a2, float b1, float b2, float c1, float c2)
{
    float x=a1;
    float a=c2-b2;
    float b=b1-c1;
    ///if(b==0) return 2000000;
    float c=(b2*c1)-(b1*c2);
    float y=-((a*a1)+c)/b;
    float dist1=fabs(y-a2);
    return dist1;
}
float disto(float a1, float a2, float b1, float b2, float c1, float c2)
{
    float y=a2;
    float a=c2-b2;
    ///if(a==0) return 2000000;
    float b=b1-c1;
    float c=(b2*c1)-(b1*c2);
    float x=-((b*a2)+c)/a;
    float dist1=fabs(x-a1);
    return dist1;
}
void verif()
{
        for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            double minn=2000000000,s=0;
                if((tri[i].x1>=tri[j].x1&&tri[i].x1<=tri[j].x2)||(tri[i].x1<=tri[j].x1&&tri[i].x1>=tri[j].x2))
                {
                    s=distv(tri[i].x1, tri[i].y1, tri[j].x1, tri[j].y1, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].x1>=tri[j].x1&&tri[i].x1<=tri[j].x3)||(tri[i].x1<=tri[j].x1&&tri[i].x1>=tri[j].x3))
                {
                    s=distv(tri[i].x1, tri[i].y1, tri[j].x1, tri[j].y1, tri[j].x3, tri[j].y3);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].x1>=tri[j].x3&&tri[i].x1<=tri[j].x2)||(tri[i].x1<=tri[j].x3&&tri[i].x1>=tri[j].x2))
                {
                    s=distv(tri[i].x1, tri[i].y1, tri[j].x3, tri[j].y3, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }

                if((tri[i].x2>=tri[j].x1&&tri[i].x2<=tri[j].x2)||(tri[i].x2<=tri[j].x1&&tri[i].x2>=tri[j].x2))
                {
                    s=distv(tri[i].x2, tri[i].y2, tri[j].x1, tri[j].y1, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].x2>=tri[j].x1&&tri[i].x2<=tri[j].x3)||(tri[i].x2<=tri[j].x1&&tri[i].x2>=tri[j].x3))
                {
                    s=distv(tri[i].x2, tri[i].y2, tri[j].x1, tri[j].y1, tri[j].x3, tri[j].y3);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].x2>=tri[j].x3&&tri[i].x2<=tri[j].x2)||(tri[i].x2<=tri[j].x3&&tri[i].x2>=tri[j].x2))
                {
                    s=distv(tri[i].x2, tri[i].y2, tri[j].x3, tri[j].y3, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }

                if((tri[i].x3>=tri[j].x1&&tri[i].x3<=tri[j].x2)||(tri[i].x3<=tri[j].x1&&tri[i].x3>=tri[j].x2))
                {
                    s=distv(tri[i].x3, tri[i].y3, tri[j].x1, tri[j].y1, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].x3>=tri[j].x1&&tri[i].x3<=tri[j].x3)||(tri[i].x3<=tri[j].x1&&tri[i].x3>=tri[j].x3))
                {
                    s=distv(tri[i].x3, tri[i].y3, tri[j].x1, tri[j].y1, tri[j].x3, tri[j].y3);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].x3>=tri[j].x3&&tri[i].x3<=tri[j].x2)||(tri[i].x3<=tri[j].x3&&tri[i].x3>=tri[j].x2))
                {
                    s=distv(tri[i].x3, tri[i].y3, tri[j].x3, tri[j].y3, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }

                if((tri[i].y1>=tri[j].y1&&tri[i].y1<=tri[j].y2)||(tri[i].y1<=tri[j].y1&&tri[i].y1>=tri[j].y2))
                {
                    s=disto(tri[i].x1, tri[i].y1, tri[j].x1, tri[j].y1, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].y1>=tri[j].y1&&tri[i].y1<=tri[j].y3)||(tri[i].y1<=tri[j].y1&&tri[i].y1>=tri[j].y3))
                {
                    s=disto(tri[i].x1, tri[i].y1, tri[j].x1, tri[j].y1, tri[j].x3, tri[j].y3);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].y1>=tri[j].y3&&tri[i].y1<=tri[j].y2)||(tri[i].y1<=tri[j].y3&&tri[i].y1>=tri[j].y2))
                {
                    s=disto(tri[i].x1, tri[i].y1, tri[j].x3, tri[j].y3, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }

                if((tri[i].y2>=tri[j].y1&&tri[i].y2<=tri[j].y2)||(tri[i].y2<=tri[j].y1&&tri[i].y2>=tri[j].y2))
                {
                    s=disto(tri[i].x2, tri[i].y2, tri[j].x1, tri[j].y1, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].y2>=tri[j].y1&&tri[i].y2<=tri[j].y3)||(tri[i].y2<=tri[j].y1&&tri[i].y2>=tri[j].y3))
                {
                    s=disto(tri[i].x2, tri[i].y2, tri[j].x1, tri[j].y1, tri[j].x3, tri[j].y3);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].y2>=tri[j].y3&&tri[i].y2<=tri[j].y2)||(tri[i].y2<=tri[j].y3&&tri[i].y2>=tri[j].y2))
                {
                    s=disto(tri[i].x2, tri[i].y2, tri[j].x3, tri[j].y3, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }

                if((tri[i].y3>=tri[j].y1&&tri[i].y3<=tri[j].y2)||(tri[i].y3<=tri[j].y1&&tri[i].y3>=tri[j].y2))
                {
                    s=disto(tri[i].x3, tri[i].y3, tri[j].x1, tri[j].y1, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].y3>=tri[j].y1&&tri[i].y3<=tri[j].y3)||(tri[i].y3<=tri[j].y1&&tri[i].y3>=tri[j].y3))
                {
                    s=disto(tri[i].x3, tri[i].y3, tri[j].x1, tri[j].y1, tri[j].x3, tri[j].y3);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }
                if((tri[i].y3>=tri[j].y3&&tri[i].y3<=tri[j].y2)||(tri[i].y3<=tri[j].y3&&tri[i].y3>=tri[j].y2))
                {
                    s=disto(tri[i].x3, tri[i].y3, tri[j].x3, tri[j].y3, tri[j].x2, tri[j].y2);
                    ///g<<s<<'\n';
                    if(s<=minn) minn=s;
                }

///                g<<minn<<'\n';
                if(minn<=k&&minn>0)
                {
                    ///g<<minn<<'\n';
                    nr++; v[i][j]=v[j][i]=minn;
                    v1[nr]={minn,{i,j}};
                    g<<minn<<" "<<i<<" "<<j<<'\n';
                }
        }
}
int compr(int v)
{
    if(t[v]==v) return v;
    t[v]=compr(t[v]);
    ///return t[v];
}
void df(int k)
{
    for(int i=1;i<=n;i++)
    if(v[k][i]&&viz[i]==0)
    {
        viz[i]=1; nr1++;
        df(i);
    }
    else if(viz[i]&&v[k][i]&&nr1>1) nr1++;
}
void df2(int k1, int s)
{
    for(int i=1;i<=n;i++)
    if(v[k1][i]&&viz[i]==0)
    {
        if(s-v[k1][i]>=0) {nr1++; viz[i]=1; s=s-v[k1][i]; df2(i,s);}
        else df2(k+1,s);
    }
    ///else if(viz[i]&&v[k][i]&&nr1>1) nr1++;
}
int main()
{
    f>>p;
    f>>n>>k;
    for(int i=1;i<=n;i++)
    {
        f>>tri[i].x1>>tri[i].y1;
        f>>tri[i].x2>>tri[i].y2;
        f>>tri[i].x3>>tri[i].y3;
    }
    verif();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            g<<v[i][j]<<" ";
        g<<'\n';
    }
    if(p==1)
    {
        nr=0;
        for(int i=1;i<=n;i++)
        {
            if(!viz[i]) {viz[i]=1; nr++; df2(i,k);}
        }
        g<<nr<<'\n';
    }
    else
    if(p==2)
    {
        nr=0;
        for(int i=1;i<=n;i++)
        {
            if(!viz[i]) {nr1=0; viz[i]=1; df(i); nr+=nr1;}
        }
        g<<nr<<'\n';
    }
    else
    {
        g<<nr<<" ";
        for(int i=1;i<=n;i++)
            t[i]=i;
        sort(v1,v1+nr+1);
        ///g<<v1[nr].first<<'\n';
        int i=1, j=nr-1;
        while(j)
        {
            int a=v1[i].second.first;
            int b=v1[i].second.second;
            g<<a<<" "<<b<<'\n';
            int x=compr(a), y=compr(b);
            ///g<<x<<" "<<y<<'\n';
            if(x!=y)
            {
                t[x]=y;
                sol.push_back({a,b});
                cost+=v1[i].first;
                j--;
            }
        i++;
        }

        g<<cost<<'\n';
        ///for(vector<pair<int,int> >::iterator it=sol.begin();it!=sol.end();it++)
           /// g<<it->first<<" "<<it->second<<'\n';
    }
    return 0;
}



/**
1
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

------>3

2
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

----->4

3
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

----->30;
**/