// https://www.infoarena.ro/problema/apm
// rezolvata cu prim - COMPLEXITATE SUPER MARE, ar ocupa aproximativ 160 GB de memorie!!
#include <algorithm>
#include <fstream>
#include <climits>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAX_N = 200000, MAX_M = 400000, INF = INT_MAX;
struct muchie {
    int c, x, y;
} e[MAX_M];
int N, M, T[MAX_N], cost;
vector <pair <int, int> > Sol;

bool cmp (muchie a, muchie b) {
    return a.c < b.c;
}
int radacina(int nod) { // Determina radacina fiecarui nod
    if (T[nod] != nod)
        T[nod] = radacina(T[nod]);
    return T[nod];
}

int main() {
    fin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        e[i].c = c, e[i].x = x, e[i].y = y;
    }
    sort(e, e + M, cmp); // Sort muchii
    for (int i = 0; i <= N; i++) // Fiecare nod are un arbore la inceput (din el insusi), deci tata[i] = i
        T[i]=i;
    int cost = 0;

    for (int i = 0; i < M; i++){
        int n1 = e[i].x;
        int n2 = e[i].y;
        if (radacina(n1) != radacina(n2)){
            cost += e[i].c;
            Sol.push_back(make_pair(n1, n2));
            T[T[n2]] = T[n1];
        }
    }
    fout << cost << '\n';
    fout << Sol.size() << '\n';
    for (int i = 0; i < Sol.size(); i++) {
        fout << Sol[i].first << ' ' << Sol[i].second << '\n';
    }

    return 0;
}