#include <cstdio>
#include <algorithm>
#define NMAX 200001

using namespace std;

FILE *fin = fopen("apm.in", "r");
FILE *fout = fopen("apm.out", "w");

int N, M, K;
int ctotal;
int T[NMAX], R[NMAX], U[NMAX];

struct list {
    int u;
    int v;
    int cost;
} G[NMAX];

bool cmp(const list &x, const list &y) {
    return x.cost < y.cost;
}

int FindSet(int c) {
    int rad, q, a;
    for(rad = c; rad != T[rad]; rad = T[rad]);
    for(q = c; q != T[q]; ) {
        a = T[q];
        T[q] = T[rad];
        q = a;
    }
    return T[rad];
}

void UnionSet(int u, int v) {
    u = FindSet(u);
    v = FindSet(v);
    if(R[u] < R[v])
        T[u] = T[v];
    else T[v] = T[u];
    if(R[u] == R[v]) ++ R[u];
}

void ReadData() {
    int i;
    fscanf(fin, "%d %d", &N, &M);
    for(i = 1; i <= M; ++ i) {
        fscanf(fin, "%d %d %d", &G[i].u, &G[i].v, &G[i].cost);
    }
}

void Kruskal() {
    int i, u, v, c;
    sort(G + 1, G + M + 1, cmp);
    for(i = 1; i <= N; ++ i) {
        T[i] = i;
        R[i] = 0;
    }
    for(i = 1; i <= M; ++ i) {
        u = G[i].u;
        v = G[i].v;
        c = G[i].cost;
        if(FindSet(u) == FindSet(v)) continue;
        UnionSet(u, v);
        U[++ K] = i;
        ctotal += c;
    }
}

int main() {
    ReadData();
    Kruskal();
    fprintf(fout, "%d\n", ctotal);
    fprintf(fout, "%d\n", N-1);
    for(int i = 1; i <= K; ++ i)
        fprintf(fout, "%d %d\n", G[U[i]].u, G[U[i]].v);
    return 0;
}