#include <fstream>
#include <algorithm>
#define NMAX 400010

using namespace std;

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

int n,C[NMAX],m,Cost;
int minim,maxim;
int cati_de1=1;

struct elem{int x; int y; int cost;} muchie[NMAX],retin[NMAX];

int comp(elem a, elem b)
{
    if(a.cost<b.cost) return 1;
    if(a.cost==b.cost && a.x<b.x) return 1;
    if(a.cost==b.cost && a.x==b.x && a.y<b.y) return 1;
    return 0;
}

int main()
{
    int i,j,z=0,k;
    fin >> n >> m;
    for(i=1;i<=m;i++)
    {
        fin >> muchie[i].x;
        fin >> muchie[i].y;
        fin >> muchie[i].cost;
        C[i]=i;
    }
    sort(muchie+1,muchie+m+1,comp);

    i=1;
    for(k=1;k<n;k++)
    {
        if(C[muchie[i].x]<C[muchie[i].y])
            minim=C[muchie[i].x],maxim=C[muchie[i].y];
        else minim=C[muchie[i].y],maxim=C[muchie[i].x];
        if(minim!=maxim)
        {
            for(j=1;j<=n;j++)   if(C[j]==maxim) C[j]=minim;
            z++;
            retin[z]=muchie[i];
            Cost+=muchie[i].cost;
        }
        do
        {
            i++;
        }
        while(C[muchie[i].x]==C[muchie[i].y]);
    }
    fout << Cost << '\n';
    fout << n-1 << '\n';
    for(i=1;i<n;i++)
        fout << retin[i].x << ' ' << retin[i].y  << '\n';
    return 0;
}