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

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

int a[400001], b[400001], c[400001], ind[400001];;
int grup[200001], rang[200001];
pair<int, int> sol[199999];

inline int find_set(int nod) {
    if (grup[nod] == nod)
        return nod;
    grup[nod] = find_set(grup[nod]);
    return grup[nod];
}

inline void union_set(int a, int b) {
    if (rang[a] < rang[b])
        grup[a] = b;
    else
        grup[b] = a;
    if (rang[a] == rang[b])
        rang[a]++;
}

bool cmp(int i, int j) {
    return c[i] < c[j];
}

int main() {
    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> a[i] >> b[i] >> c[i];
    }

    for (int i = 0; i < m; i++)
        ind[i] = i;

    sort(ind, ind + m, cmp);
    for (int i = 1; i <= n; i++) {
        grup[i] = i;
        rang[i] = 0;
    }

    int ra, rb, suma = 0, indice = 0;
    for (int i = 0; i < m; i++) {
        ra = find_set(a[ind[i]]);
        rb = find_set(b[ind[i]]);
        if (ra != rb) {
            union_set(ra, rb);
            sol[indice].first = a[ind[i]];
            sol[indice++].second = b[ind[i]];
            suma += c[ind[i]];
        }
    }

    out << suma << endl << n - 1 << endl;
    for (int i = 0; i < n - 1; i++) {
        out << sol[i].first << " " << sol[i].second << endl;
    }
    return 0;
}