#include <fstream>
#include <algorithm>
#define MMAX 400000
#define NMAX 200000

using namespace std;
FILE * fin=fopen("apm.in", "r");
FILE * fout=fopen("apm.out", "w");

int n, m, nr;
struct muchie
{
int x, y;
int cost;
};
muchie L[MMAX];
int APM[NMAX]; // retin indicii celor n-1 muchii selectate
int conex[NMAX];
int costapm;

void citire();
void kruskal();
void unific(int, int);
bool cmp(muchie, muchie);
void afisare();

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

void kruskal()
{
int mcrt=0;
sort(L, L+m, cmp);
for (nr=1; nr<=n-1; mcrt++)
    {
        // selectez o muchie de cost minim neselectata
        if (conex[L[mcrt].x]!=conex[L[mcrt].y]) // daca extremitatile muchiei selectate sunt in comp. conexe diferite
            {
                APM[nr++]=mcrt;
                costapm+=L[mcrt].cost;
                unific(L[mcrt].x, L[mcrt].y);
            }
    }
}

void unific(int a, int b)
{
int i, min, max;
// stabilesc care din comp. conexe are ordinul mai mic
min=conex[a]; max=conex[b];
if (conex[a]>conex[b])
    {min=conex[b]; max=conex[a];}
for (i=1; i<=n; i++)
    if (conex[i]==max)
        conex[i]=min;
}

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

void afisare()
{
int i;
fprintf(fout, "%d\n%d\n", costapm, nr-1);
for (i=1; i<nr; i++)
    fprintf(fout, "%d %d\n", L[APM[i]].x, L[APM[i]].y);
fclose(fout);
}

void citire()
{
int i;
fscanf(fin, "%d %d", &n, &m);
for (i=0; i<m; i++)
    fscanf(fin, "%d %d %d",&L[i].x, &L[i].y, &L[i].cost);
for (i=1; i<=n; i++)
    conex[i]=i;
}