#include <fstream>
#include <algorithm>
#define NMAX 200009
#define MMAX 400009
using namespace std;

FILE * fin =fopen ("apm.in", "r");
FILE * fout =fopen("apm.out", "w");

struct graf
{
    int a, b, c;
};

int n, m;
int cost;
int h[NMAX], tata[NMAX], sol[NMAX];
graf muchie[MMAX];

void citire ();
void krushkal ();
void Union(int x, int y);
int Find (int x);
bool compara (const graf &x,const graf &y);
void afisare();

int main()
{
    citire();
    krushkal();
    afisare();
    return 0;
}

void citire ()
{

    int i;
    fscanf(fin, "%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
        fscanf(fin, "%d %d %d\n", &muchie[i].a, &muchie[i].b, &muchie[i].c );
    sort(muchie+1, muchie+m+1, compara );
}

bool compara (const graf &x,const graf &y)
{
    return x.c<y.c;
}

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

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

void krushkal ()
{
    int i, nr=0, ra, rb;
    for(i=1; nr<n-1; ++i)
    {
        ra=Find(muchie[i].a);
        rb=Find(muchie[i].b);
        if(ra!=rb)
        {
            cost=cost+muchie[i].c;
            sol[++nr]=i;
            Union (ra, rb);
        }
    }
}

void afisare()
{
    int i;
    fprintf(fout, "%d\n", cost);
    fprintf(fout, "%d\n", n-1);
    for(i=1; i<n; ++i)
        fprintf(fout, "%d %d\n", muchie[sol[i]].a, muchie[sol[i]].b);
    fclose(fout);
}