#include <fstream>
#include <algorithm>
#define NMAX 200050
#define MMAX 400050
using namespace std;

ofstream fout("apm.out");

struct muchie
{
    int x, y;
    double c;
};
muchie cost[MMAX];
int n, m, nr;
int sol[NMAX], conex[NMAX];
double total;

void citire();
void initializare();
bool compara (muchie a, muchie b);
void det();
void afisare();

int main()
{
    citire();
    det();
    afisare();
    return 0;
}

void citire()
{
    ifstream fin ("apm.in");
    int i;
    fin>>n>>m;
    for(i=0; i<m; ++i)
    {
        fin>>cost[i].x>>cost[i].y>>cost[i].c;
    }
    initializare();
    //sortare
    sort(cost, cost+m, compara);
}

void initializare()
{
    int i;
    for(i=1; i<=n; ++i)
        conex[i]=i;
}

bool compara (muchie a, muchie b)
{
    return a.c<b.c;
}

void det()
{
    int i, j, minim, maxim;
    for(i=0; nr<n; ++i)
    {
        if(conex[cost[i].x]!=conex[cost[i].y])
        {
            sol[++nr]=i;
            total+=cost[i].c;
            if(conex[cost[i].x]>conex[cost[i].y])
            {
                maxim=conex[cost[i].x];
                minim=conex[cost[i].y];
            }
            else
            {
                maxim=conex[cost[i].y];
                minim=conex[cost[i].x];
            }
            for(j=1; j<=n; ++j)
                if(conex[j]==maxim)
                    conex[j]=minim;

        }

    }
}

void afisare()
{
    int i;
    fout<<total<<'\n'<<nr-1<<'\n';
    for(i=1; i<n; ++i)
        fout<<cost[sol[i]].x<<' '<<cost[sol[i]].y<<'\n';
}