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

#define MAXM 400000+10
#define MAXN 200000+10

using namespace std;

struct poo {
    int x, y, c;
} v[MAXM], muchii[MAXM];

FILE *f, *g;

int n, m, k, cost;
int tata[MAXN];

bool cum (poo a, poo b)
{
    return a.c < b.c;
}
void ReadInputData ()
{
    fscanf(f, "%d %d\n", &n, &m);
    for (int i = 1; i <= m; i++)
        fscanf(f, "%d %d %d", &v[i].x, &v[i].y, &v[i].c);
    sort(v+1, v+m+1, cum);
}
int cauta (int nod)
{
    if (tata[nod] != nod)
        tata[nod] = cauta(tata[nod]);
    return tata[nod];
}
void uneste (int p1, int p2, int pozitie)
{
    muchii[++k] = v[pozitie];
    cost += v[pozitie].c;
    tata[p1]=p2;
}
void WriteOutputData ()
{
    fprintf(g, "%d\n%d\n", cost, k);
    for (int i = 1; i <= k; i++)
        fprintf(g, "%d %d\n", muchii[i].x, muchii[i].x);

}
int main()
{
    f = fopen("apm.in", "r");
    g = fopen("apm.out", "w");

    ReadInputData();

    for (int i = 1; i <= n; i++)
        tata[i] = i;

    for (int i = 1; i <= m; i++)
    {
        int p1 = cauta(v[i].x);
        int p2 = cauta(v[i].y);
        if (p1 != p2 || !p1)
            uneste(p1, p2, i);
    }

    WriteOutputData();

    fclose(f);
    fclose(g);

    return 0;
}