#include <stdio.h>
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 200000
#define MMAX 400000

struct MUCHIE {int x; int y; int c;};
MUCHIE muchie[MMAX];
int comp[NMAX];
int sol[MMAX];
int TOTAL,n,k,m,contor;

void citire();
void sortare(int,int);
void kruskal();
void afisare();

int main()
{
    citire();
    sortare(1,m);
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    FILE * fin=fopen(IN,"r");

    int i;
    fscanf(fin,"%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)
        comp[i]=i;
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&muchie[i].x,&muchie[i].y,&muchie[i].c);
        TOTAL=TOTAL+muchie[i].c;
    }

    fclose(fin);
}

void sortare(int stanga, int dreapta)
{
    int i,j;
    MUCHIE a;
    if(stanga<dreapta)
    {
        a=muchie[stanga];
        i=stanga; j=dreapta;

        while(i<j)
        {
            while(i<j && muchie[j].c>=a.c)
                j--;
            muchie[i]=muchie[j];
            while(i<j && muchie[i].c<=a.c)
                i++;
            muchie[j]=muchie[i];
        }
        muchie[i]=a;
        sortare(stanga,i-1);
        sortare(i+1,dreapta);
    }
}

void kruskal()
{
    int i,j,minim,maxim;

    for(i=1;contor<n-k;i++)
    {
        if(comp[muchie[i].x]!=comp[muchie[i].y])
        {
            TOTAL=TOTAL-muchie[i].c;

            contor++;
            sol[i]=1;
            minim=comp[muchie[i].x];
            maxim=comp[muchie[i].y];
            if(comp[muchie[i].x]>comp[muchie[i].y])
            {
                minim=comp[muchie[i].y];
                maxim=comp[muchie[i].x];
            }
            for(j=1;j<=m;j++)
                if(comp[j]==maxim)
                    comp[j]=minim;
        }
    }
}

void afisare()
{
    FILE * fout=fopen(OUT,"w");

    int i;
    fprintf(fout,"%d\n%d\n",TOTAL,m-contor);
    for(i=1;i<=m;i++)
    {
        if(sol[i]==0)
        fprintf(fout,"%d %d\n",muchie[i].x,muchie[i].y);
    }

    fclose(fout);
}