#include <fstream>
#define NMAX 200005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
    { int x, y, c; } G[400005], sol[200005];
int tata[NMAX], h[NMAX];
int n, m, k;
int cmin;


void citire();
void kruskal();
int Find(int x2);
void Union(int x, int y);
void comb_heap(int i, int n);
void creare_heap();
muchie extragere(int &n);

int main()
{
    citire();
    creare_heap();
    kruskal();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>m>>k;
    for(i=1; i<=m; i++)
       fin>>G[i].x>>G[i].y>>G[i].c;
}

void kruskal()
{
    int i, nr;
    int c1, c2;
    muchie minim;
    for(i=1; i<=n-1; i++)
    {
        minim=extragere(m);
        c1=Find(minim.x);
        c2=Find(minim.y);
        if(c1!=c2)
        {
            cmin+=minim.c;
            Union(c1, c2);
            sol[i]=minim;
        }
        else
            i--;
    }
    fout<<cmin<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
}

int Find(int x)
{
    int rad, aux;
    rad=x;
    while(tata[rad]) rad=tata[rad];
    aux=x;
    while(tata[x])
    {
        aux=x; x=tata[x];
        tata[aux]=rad;
    }
    return rad;
}

void Union(int x,int y)
{
    if(h[x]>h[y]) tata[y]=x;
    else
    {
        tata[x]=y;
        if(h[x]==h[y]) h[y]++;
    }
}

void comb_heap(int i, int n)
{
    int fiu, tata, x;
    muchie aux;
    tata=i; fiu=2*i;
    x=G[i].c; aux=G[i];
    while(fiu<=n)
    {
        if(fiu+1<=n)
            if(G[fiu].c>=G[fiu+1].c)
                fiu++;
        if(x>G[fiu].c)
        {
            G[tata]=G[fiu];
            tata=fiu; fiu=2*tata;
        }
        else break;
    }
    G[tata]=aux;
}

muchie extragere(int &n)
{
    muchie x=G[1];
    G[1]=G[n];
    n--;
    comb_heap(1,n);
    return x;
}

void creare_heap()
{
    int i;
    for(i=m/2; i>=1; i--)
        comb_heap(i, m);
}