/**

*/
#include<iostream>
#include<fstream>
#include<string.h>
#include<algorithm>

using namespace std;

int N,M,TT[200001],ma[400001],cost=0;
ifstream fin;
ofstream fout("apm.out");
struct muchie
{
    int x,y,c;
}e[400001];

void citire()
{
    fin.open("apm.in");
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>e[i].x>>e[i].y>>e[i].c;
    }
}

bool compare(muchie n1,muchie n2){return n1.c<n2.c;}

int Root(int x)
{
    while(TT[x]!=x)
        x=TT[x];
    return x;
}

void init()
{
    for(int i=1;i<=N;i++)
        TT[i]=i;
}

void Unite(int x,int y)
{
    TT[x]=y;
}

void Niko()
{
    int edge=0,k=1;
    while(edge<N-1)
    {
        if(Root(e[k].x)!=Root(e[k].y))
        {

            Unite(Root(e[k].x),Root(e[k].y));
            cost=cost+e[k].c;
            ma[edge]=k;
            edge++;
        }
        k++;
    }
}

void afisare()
{
    fout<<cost<<'\n';
    fout<<N-1<<'\n';
    for(int i=0;i<N-1;i++)
        fout<<e[ma[i]].x<<' '<<e[ma[i]].y<<'\n';

}
int main()
{
    citire();
    sort(e+1,e+M+1,compare);
    init();
    Niko();
    afisare();
    return 0;
}