#include <fstream>
#include <algorithm>
#define DMAX 200001
#define MMAX 400001
using namespace std;

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

struct pack{
    int x, y;
    int cost;
};

struct pack muchii[MMAX];
int APM[DMAX];//indicii muchiilor selectate
int costAPM;
int lg_APM;
int n, m, conex[DMAX];

bool cmp (struct pack, struct pack);
void citire();
void kruskal();
void afisare();

int main()
{
    citire();
    sort (muchii+1, muchii+m+1, cmp);
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>m;
    for (i=1; i<=m; ++i)
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    for (i=1; i<=n; ++i)
        conex[i]=i;
    fin.close();
    return;
}

bool cmp (struct pack a, struct pack b)
{
    return a.cost<b.cost;
}

void kruskal()
{
    int i, j, minim, maxim; // este necesar sa am min si max. nu puteam compara direct
    for (i=1; i<=m; ++i)
    {
        //pot selecta muchia i?
        if (conex[muchii[i].x]!=conex[muchii[i].y])
        {
            costAPM=costAPM+muchii[i].cost;
            APM[++lg_APM]=i;

            minim=conex[muchii[i].x]; maxim=conex[muchii[i].y];
            if (maxim<minim)
                {
                    minim=conex[muchii[i].y];
                    maxim=conex[muchii[i].x];
                }
            for (j=1; j<=n; ++j)
                if (conex[j]==maxim)
                    conex[j]=minim;
        }
    }
    return;
}

void afisare()
{
    int i;
    fout<<costAPM<<"\n"<<lg_APM<<"\n";
    for (i=1; i<=n-1; ++i)
        fout<<muchii[APM[i]].x<<" "<<muchii[APM[i]].y<<"\n";
    fout.close();
    return;

}