#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
 
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct kru {
    int nod1, nod2, cost;
}v[200001], fin[200001];
int n, m, T[200001], rang[150001], nr, sum; 

bool srt(kru x, kru y) {
    return x.cost < y.cost;
}

int Radacina(int k) {
    if (T[k] == 0)
        return k;
    else {
        int x = Radacina(T[k]);
        T[k] = x;
        return x;
    }
}

int Kruskal() {
    int nr = 0, r1, r2;
    for (int i = 1; i <= m; i++) {
        r1 = Radacina(v[i].nod1), r2 = Radacina(v[i].nod2);
        if (r1 != r2) {
            if (rang[r1] < rang[r2])
                T[r1] = r2;
            else {
                T[r2] = r1;
                if (rang[r1] == rang[r2])
                    rang[r1]++;
            }
            sum += v[i].cost;
            fin[++nr] = v[i];
            if (nr == n - 1) return sum;
        }
    }
    return -1;
}

int main() {
    in >> n >> m;
    for (int i = 1; i <= m; i++)
        in >> v[i].nod1 >> v[i].nod2 >> v[i].cost;
    sort(v + 1, v + m + 1, srt);
    out << Kruskal() << '\n' << n - 1 << '\n';
    for (int i = 1; i < n; i++)
        out << fin[i].nod1 << ' ' << fin[i].nod2 << '\n';
    return 0;
}