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

using namespace std;

struct muchii {
    int x, y, c;
} V[400001];

bool sort_type (muchii a, muchii b) {
    return a.c < b.c;
}

int P[400001];
int sol[200001];
bool viz[200001];

int main() {
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    int M,N,i,ct;
    sol[0] = 0;
    ct = 0;
    scanf ("%d %d", &N, &M);
    for (i = 1; i <= M; i++)
        scanf("%d %d %d", &V[i].x, &V[i].y, &V[i].c);
    V[0].x = M;
    sort(V + 1, V + M + 1, sort_type);
    for (i = 1; i <= N; i++)
        P[i] = i;
    int count = 0, cost = 0, nr1, nr2;
    i = 1;
    //kruskal
    /* while (count < N-1) {
       if (P[V[i].x] != P[V[i].y]) {
        ++count;
        ++sol[0];
        sol[sol[0]] = i;
        cost += V[i].c;
        nr1 = P[V[i].x];
        nr2 = P[V[i].y];
        for (int j = 1; j <= N; j++)
            if (P[j] == nr2)
                P[j] = nr1;
       }
       ++i;
    }
    */
    //prim
    for (i = 1; i <= N; i++)
        viz[i] = 0;
    viz[V[1].x] = 1;
    viz[V[1].y] = 1;
    sol[1] = 1;
    int nrsol = 1;
    cost += V[1].c;
    for (count = 1; count <= N - 2; count++) {
        i = 2;
        while (viz[V[i].x] == viz[V[i].y])
            ++i;
        viz[V[i].x] = 1;
        viz[V[i].y] = 1;
        cost += V[i].c;
        ++nrsol;
        sol[nrsol] = i;
    }
    printf ("%d\n%d\n", cost, N-1);
    for (i = 1; i <= N-1; i++)
        printf("%d %d\n", V[sol[i]].x, V[sol[i]].y);
    return 0;
}