#include <iostream>
#include <fstream>
#define NMax 200002
#define MMax 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
////////////////////////////////////////
typedef struct
{
    int x,y,c;
}muchie;
muchie g[MMax];
int c[NMax],a[NMax],m,n;
////////////////////////////////////////
void citireInit();
void sortMuchii(int,int);
void rezolva();
void afisare();
////////////////////////////////////////
int main ()
{int i;
    citireInit();
    sortMuchii(1,m);
    rezolva();
    afisare();
}
void citireInit()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=n;i++) c[i]=i;
    for (i=1;i<=m;i++)
        fin>>g[i].x>>g[i].y>>g[i].c;
}
void sortMuchii(int st, int dr)
{
    int i,j;
    muchie x;
    if (st<dr)
    {
        x=g[st];
        i=st;
        j=dr;
        while (i<j)
        {
            while (i<j && g[j].c>=x.c) j--;
            g[i]=g[j];
            while (i<j && g[i].c<=x.c) i++;
            g[j]=g[i];
        }
        g[i]=x;
        sortMuchii(st,i-1);
        sortMuchii(i+1,dr);
    }
}
void rezolva ()
{
    int i,j,minv,maxv,nrMuchii=0;
    for (i=1;nrMuchii<n-1;i++)
    {
        if (c[g[i].x]!=c[g[i].y])
        {
            a[++nrMuchii]=i;
            if (c[g[i].x]<c[g[i].y])
            {
                maxv=c[g[i].y];
                minv=c[g[i].x];
            }
            else
            {
                maxv=c[g[i].x];
                minv=c[g[i].y];
            }
            for (j=1;j<=n;j++)
                if (c[j]==maxv) c[j]=minv;
        }
    }
}
void afisare ()
{
    int i,sum=0;
    for (i=1;i<=n-1;i++)
        sum=sum+g[a[i]].c;
    fout<<sum<<'\n';
    fout<<n-1<<'\n';
    for (i=1;i<=n-1;i++)
        fout<<g[a[i]].x<<" "<<g[a[i]].y<<'\n';
}