#include <stdio.h>
#include <algorithm>

using namespace std;
const int VMAX = 200000, EMAX = 400000;

void init();
int UF_find(int e);
bool UF_union(int e1, int e2);

struct edge
{
    int v1, v2, w;
};
bool operator <(const edge& x, const edge& y) {
    return x.w < y.w;
}

edge edges[EMAX], apm[VMAX - 1];
int boss[VMAX + 1];

int main()
{
    int nre, nrv, i, minw, j;
    FILE *fin = fopen("apm.in", "r");
    fscanf(fin, "%d%d", &nrv, &nre);
    for (i = 0; i < nre; i++)
        fscanf(fin, "%d%d%d", &edges[i].v1, &edges[i].v2, &edges[i].w);
    fclose(fin);
    sort(edges, edges + nre);

    init();
    j = minw = 0;
    for (i = 0; i <= nrv; i++)
    for (i = 0; i < nre; i++)
    {
        if (UF_union(edges[i].v1, edges[i].v2) == 1)
        {
            apm[j++] = edges[i];
            minw += edges[i].w;
        }
    }
    FILE *fout = fopen("apm.out", "w");
    nrv--;
    fprintf(fout, "%d\n%d\n", minw, nrv);
    for (i = 0; i < nrv; i++)
        fprintf(fout, "%d %d\n", apm[i].v1, apm[i].v2);
    fclose(fout);
    return 0;
}

void init()
{
    for (int i = 1; i <= VMAX; i++)
        boss[i] = i;
}
int UF_find(int e)
{
    if (boss[e] == e)
        return e;
    return boss[e] = UF_find(boss[e]);
}
bool UF_union(int e1, int e2)
{
    int boss1 = UF_find(e1);
    int boss2 = UF_find(e2);
    if (boss1 == boss2)
        return 0;

    boss[boss1] = boss2;
    return 1;
}