#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 400100
#define pb push_back

using namespace std;

FILE *f = freopen("apm.in", "r", stdin);
FILE *g = freopen("apm.out", "w", stdout);

vector <int> ANS;

int X[NMAX], Y[NMAX], IND[NMAX], FATHER[NMAX], N, M, COST[NMAX];
int COST_SOL = 0;

int find_(int x) {
   if(FATHER[x] == x) return x;
   FATHER[x] = find_(FATHER[x]);
   return FATHER[x];
}

void unite_(int x, int y) {
    FATHER[find_(y)] = find_(x);
}

bool cmp(int x, int y) {
    return COST[x] < COST[y];
}

void read() {
    scanf("%d%d", &N, &M);

    for(int i = 1; i<=M; i++) {
        scanf("%d%d%d", &X[i], &Y[i], &COST[i]);
        IND[i] = i;
    }
    sort(IND + 1, IND + M + 1, cmp);

    for(int i = 1; i<=N; i++)
        FATHER[i] = i;
}
void solve() {
    for(int i = 1; i<=M; i++) {
        if(find_(X[IND[i]]) != find_(Y[IND[i]])){
            COST_SOL += COST[IND[i]];
            ANS.pb(IND[i]);
            unite_(X[IND[i]], Y[IND[i]]);
        }
    }
}

void write() {
    printf("%d\n", COST_SOL);
    printf("%d\n", ANS.size());

    for(int i = 0; i<ANS.size(); i++) {
        printf("%d %d\n", X[ANS[i]], Y[ANS[i]]);
    }
}
int main() {
    read();
    solve();
    write();
    return 0;
}