#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 400005;

pair <int,int> Rez[NMAX];

int N,M;
int TT[NMAX],RG[NMAX],k;
int Total;

struct Muchie{
    int x,y,c;
}X[NMAX];


bool Compare(Muchie a,Muchie b)
{
    return a.c<b.c;
}

void Citire()
{
    f>>N>>M;
    for(int i=1;i<=M;i++){
        f>>X[i].x>>X[i].y>>X[i].c;
    }
    sort(X+1,X+M+1,Compare);
}

int Find(int nod)
{
    while(TT[nod]!=nod){
        nod=TT[nod];
    }
    return nod;
}

void Unire(int x,int y)
{
    if(RG[x]<RG[y]){
        TT[x]=y;
    }else{
        if(RG[x]>RG[y]){
            TT[y]=x;
        }else{
            TT[x]=y;
            RG[y]++;
        }
    }
}

void Kruskal()
{
    for(int i=1;i<=M;i++){
        int Tata_X=Find(X[i].x);
        int Tata_Y=Find(X[i].y);
        if(Tata_X!=Tata_Y){
            Unire(Tata_X,Tata_Y);
            Rez[++k].first=X[i].x;
            Rez[k].second=X[i].y;
            Total=Total+X[i].c;
        }
    }
}

int main()
{
    Citire();
    for(int i=1;i<=M;i++){
        RG[i]=1;
        TT[i]=i;
    }
    Kruskal();
    g<<Total<<'\n';
    g<<N-1<<'\n';
    for(int i=1;i<=k;i++){
        g<<Rez[i].first<<" "<<Rez[i].second<<'\n';
    }
    f.close();
    g.close();
    return 0;
}