#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
{
    int32_t x, y, c;
}a[400001], muc[400001];
void quicksort(int32_t st, int32_t dr)
{
    int32_t i=st, j=dr, pivot=muc[(st+dr)/2].c;
    while(i<=j)
    {
        while((muc[i].c<pivot)&&(i<dr)) i++;
        while((muc[j].c>pivot )&&(j>st)) j--;
        if(i<=j)
        {
            swap(muc[i], muc[j]);
            i++;
            j--;

        }
    }
    if(st<j) quicksort(st, j);
    if(i<dr) quicksort(i, dr);

}
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;
    }

    ///sortezi de la 1 la m muchiile in fct de cost
    quicksort(1, m);
    ///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]))&&(muc[i].x!=j)&&(muc[i].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;
}