#include <bits/stdc++.h>
using namespace std;
#define NMAX 200005
#define NMAXMUCHI 400002
#define infile "apm.in"
#define outfile "apm.out"
typedef struct {int x, y , cost;}Muchie;
Muchie G[NMAXMUCHI];
int n,m;
int A[NMAX],C[NMAX];

void citire_graf();
void sortare_muchii(int , int);
void Afisare();
int main()
{
    citire_graf();
    sortare_muchii(1,m);
    int  nrm = 0;
    int minim,maxim;
    for(int i=1;nrm<n-1;i++)
    {
        if(C[G[i].x] != C[G[i].y])
        {
            A[++nrm] =i;
            minim = min(C[G[i].x],C[G[i].y]);
            maxim = max(C[G[i].x],C[G[i].y]);
            for(int j=1;j<=n;++j)
                if(C[j] == maxim)
                    C[j]=minim;
        }
    }
    Afisare();
    return 0;
}

void citire_graf()
{
    FILE *fin =fopen(infile,"r");
    fscanf(fin,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        //fin>>G[i].x>>G[i].y>>G[i].cost;
        fscanf(fin,"%d %d %d",&G[i].x,&G[i].y,&G[i].cost);
    }
    for(int i=1;i<=n;++i)
        C[i]=i;
    fclose(fin);
}

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

void Afisare()
{
    int price =0;
    for(int i=1;i<n;++i)
    {
       /// printf("[%d,%d] cost = %d\n",G[A[i]].x , G[A[i]].y , G[A[i]].cost);
        price+=G[A[i]].cost;
    }
    FILE *fout = fopen(outfile,"w");
    //fout<<price<<endl<<n-1<<endl;
    fprintf(fout,"%d\n%d\n",price,n-1);
    for(int i=1;i<n;++i)
    {
       // fout<<G[A[i]].x<<' '<<G[A[i]].y<<endl;
       fprintf(fout,"%d %d\n",G[A[i]].x,G[A[i]].y);
    }
    fclose(fout);
}