#include <fstream>
#include <algorithm>
#define NMAX 200001
#define MMAX 400001

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie {int x, y; double cost;};
Muchie g[MMAX];
int n, m;
double cost_apm;
int apm[NMAX]; //retin indicii celor n-1 muchii selectate
int conex[NMAX];

void citire();
int compara(Muchie, Muchie);
void kruskal();
void afisare();


int main()
{
    citire();
    sort(g, g+m, compara);
    kruskal();
    afisare();

    return 0;
}
void citire()
{
    int i;
	fin>>n>>m;
	for (i=0; i<m; ++i)
		fin>>g[i].x>>g[i].y>>g[i].cost;
    for(i=1; i<=n; i++)
        conex[i]=i;
}
int compara(Muchie a, Muchie b)
{
    return a.cost<b.cost;
}
void kruskal()
{
    int i, j, maxim, minim;
    int nrm=0; //nr de muchii selectate
    for(i=0; nrm<n-1 ; i++)
        {
        if(conex[g[i].x]!=conex[g[i].y])
            {
            apm[++nrm]=i;
            cost_apm=cost_apm+g[i].cost;
            if(conex[g[i].x]>conex[g[i].y])
                {
                minim=conex[g[i].y];
                maxim=conex[g[i].x];
                }
            else
                {
                minim=conex[g[i].x];
                maxim=conex[g[i].y];
                }
            for(j=1; j<=n; j++)
                if( conex[j]==maxim)
                    conex[j]=minim;
            }
        }
}
void afisare()
{
    int i;
    fout<<cost_apm<<'\n'<<n-1<<'\n';
    for(i=1; i<=n-1; i++)
        fout<<g[apm[i]].y<<' '<<g[apm[i]].x<<'\n';
}