#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int i,j,c;
};

int n,m,cost;

muchie M[400001];
int CC[200001];
int NrM[200001];

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>M[i].i>>M[i].j>>M[i].c;
}

void afis()
{
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(int i=1;i<n;i++)
    {
        int k=NrM[i];
        g<<M[k].i<<' '<<M[k].j<<'\n';
    }

}

int comp(const muchie &a ,const muchie &b)
{
    /**if(a.c<=b.c)return 1;
        else return 0;*/
    return a.c < b.c;
}

void Kruskal()
{
    sort(M+1,M+m+1,comp);///[1,m+1]
    for(int i=1;i<=n;i++) ///La inceput fiecare nod constituie o comp conexa
        CC[i]=i;
    int k=1; ///Incepem cu prima muchie
    for(int l=1;l<n;l++)
    {
        while(CC[M[k].i]==CC[M[k].j])///Cautam o muchie ale carei capete sunt din c.c diferite
            k++;
        NrM[l]=k; ///Marcam selectarea muchiei k
        cost+=M[k].c;
        int ccj=CC[M[k].j];///Unificam componentele conexe ale lui i si j
        for(int i=1;i<=n;i++)
            if(CC[i]==ccj)
                CC[i]=CC[M[k].i];
    }
}


int main()
{
    citire();
    Kruskal();
    afis();
    return 0;
}