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

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[200000];

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;
    while (count < N-1) {
       if (P[V[i].x] != P[V[i].y]) {
      //  cout<<P[3]<<" "<<P[8]<<endl;
        ++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;
    }
   // for (i = 1; i <= N; i++)
   // printf ("%d ", P[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;
}