#include <cstdio>
#define NMAX 260
#define MMAX 33000

using namespace std;

FILE *fin,*fout;

int n,m,k,cate,indice;
int grup[NMAX],use[MMAX];
int minim,maxim,s;
struct el{int x; int y; int cost;} muchie[MMAX];

void sorteaza(int,int);

int main()
{
    fin=fopen("urgenta.in","r");
    fout=fopen("urgenta.out","w");
    int i,j;
    fscanf(fin,"%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)
        grup[i]=i;
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&muchie[i].x,&muchie[i].y,&muchie[i].cost);
    }
    sorteaza(1,m);
    //sortez dupa cost
    cate=n;
    //muchiile sortate in ordine crescatoare
    indice=0;
    while(cate!=k)
    {
        indice++;
        if(grup[muchie[indice].x]!=grup[muchie[indice].y])
        {
            cate--;
            use[indice]=1;
            use[0]++;
            if(grup[muchie[indice].x]<grup[muchie[indice].y])
            {
                minim=grup[muchie[indice].x];
                maxim=grup[muchie[indice].y];
            }
            else
            {
                 minim=grup[muchie[indice].y];
                 maxim=grup[muchie[indice].x];
            }
            for(j=1;j<=n;j++)
                if(grup[j]==maxim) grup[j]=minim;
        }
    }
    for(i=1;i<=m;i++)
        if(use[i]==0)
            s+=muchie[i].cost;
    fprintf(fout,"%d\n%d\n",s,m-use[0]);
    for(i=1;i<=m;i++)
    if(use[i]==0)
    {
        fprintf(fout,"%d %d\n",muchie[i].x,muchie[i].y);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}

void sorteaza(int st, int dr)
{
    int i,j;
    el x;
    if(st<dr)
    {
        x=muchie[st];
        i=st;
        j=dr;
        while(i<j)
        {
            while(i<j && muchie[j].cost>=x.cost)   j--;
            muchie[i]=muchie[j];
            while(i<j && muchie[i].cost<=x.cost)   i++;
            muchie[j]=muchie[i];
        }
        muchie[i]=x;
        sorteaza(st,i-1);
        sorteaza(i+1,dr);
    }
}