#include <stdio.h>
#define IN "urgenta.in"
#define OUT "urgenta.out"
#define NMAX 300
#define MMAX 33000

struct MUCHIE {int x; int y; int c;};
MUCHIE muchie[MMAX];
int comp[NMAX], replace[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);
    }
}

int min(int a, int b) {
    if (a <= b) return a;

    return b;
}

int max(int a, int b) {
    if (a >= b) return a;

    return b;
}

int unionComponente(int x, int y) {
    replace[comp[x]] = y;
}

int find(int x) {
    return replace[comp[x]] != 0 ? replace[comp[x]] : comp[x];
}

void kruskal()
{
    int i,j, x, y, cX, cY, 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;

            x = muchie[i].x;
            y = muchie[i].y;

            cX = find(x);
            cY = find(y);

            minim = min(cX, cY);
            maxim = max(cX, cY);

            unionComponente(maxim, 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);
}