#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("apm.in", ios::in);
fstream f2("apm.out", ios::out);
///kruskal:
///tii minte muchiile si costurile lor intr-un struct
///in v[i] tii minte din al catalea arbore face parte nodul i
///initial v[i]=i, spui ca toate nodurile fac parte din cate un alt arbore
///apm se formeaza unind 2 apm distincti printr-o muchie de cost minim
///pornind de la ideea asta, vei "adauga" la apm n-1 muchii
///ai sortat cresc dupa cost vect de muchii, alegi n-1 muchii pe care le memo
///in  struct a, cu conditia ca extremitatile  muchiei sa faca parte din apm uri diferiti
///pt fiecare muchie adaugata reactualizezi costul
int32_t n, m, v[200001], nr, cost;
struct muchii
{
    int x, y, c;
}a[400001], muc[400001];
int main()
{
    int32_t i, j, x, y, c;
    f1>>n>>m;

    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        muc[i].x=x;
        muc[i].y=y;
        muc[i].c=c;
    }

    for(i=1; i<m; i++)
        for(j=i+1; j<=m; j++)
            if(muc[i].c>muc[j].c ) swap(muc[i], muc[j]);

    ///init
    for(i=1; i<=n; i++) v[i]=i;

    for(i=1; nr<(n-1); i++)
        if(v[muc[i].x]!=v[muc[i].y])
    {
        ///selectezi muchia
        nr++;
        a[nr].x=muc[i].x;
        a[nr].y=muc[i].y;
        a[nr].c=muc[i].c;

        ///unifici cei doi arbori pastrand in v[i]=v[x] sau v[y] va arborelui minim
        int32_t mini=v[muc[i].x];
        if(mini>v[muc[i].y]) mini=v[muc[i].y];
        for(j=1; j<=n; j++)///(x!=j)&&(y!=j) ca sa fii sigura ca nu modifici val din max(v[x], v[y])
            ///ca mai apoi sa nu poti gasi muchiile = acest maxim
            if(((v[j]==v[muc[i].x])||(v[j]==v[muc[i].y]))&&(x!=j)&&(y!=j)) v[j]=mini;
        v[muc[i].x]=mini;
        v[muc[i].y]=mini;

        ///reactualizezi costul
        cost+=muc[i].c;
    }

    ///afisarea
    f2<<cost<<"\n"<<nr<<"\n";
    for(i=1; i<n; i++)
       f2<<a[i].x<<" "<<a[i].y<<"\n";

    return 0;
}