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

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

struct pack muchii[MMAX];
int APM[DMAX];//indicii muchiilor selectate
int cost_APM, 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()
{
    FILE*fin=fopen("apm.in", "r");
    int i;
    fscanf(fin, "%d %d", &n, &m);
    for (i=1; i<=m; ++i)
        fscanf(fin, "%d %d %d", &muchii[i].x, &muchii[i].y, &muchii[i].cost);

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

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

void kruskal()
{
    int i, j, minimus, maximus;
    for (i=1; i<=m; ++i)
    {
        if (lg_APM==n-1)
            break;
        //pot selecta muchia i?
        if (conex[muchii[i].x]!=conex[muchii[i].y])
        {
            cost_APM+=muchii[i].cost;
            APM[++lg_APM]=i;

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

void afisare()
{
    FILE*fout=fopen ("apm.out", "w");
    int i;
    fprintf(fout, "%d\n%d\n", cost_APM, lg_APM);
    for (i=1; i<=n-1; ++i)
        fprintf(fout, "%d %d\n", muchii[APM[i]].x, muchii[APM[i]].y);
    fclose(fout);
    return;

}