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

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

const int N = 2e5 + 5;

vector <pair <int, pair <int, int> > > mc;
vector <pair <int, int> > msol;

int n, m, sol, tata[N], use;

int find(int x) {
    if (tata[x] != x)
        tata[x] = find(tata[x]);
    return tata[x];
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x > y)
        x^= y, y^= x, x^= y;
    tata[x] = y;
}

int main() {
    fin >> n >> m;
    for (int x, y, c; m; --m) {
        fin >> x >> y >> c;
        mc.push_back(make_pair (c, make_pair (x, y)));
    }
    sort(mc.begin(), mc.end());
    for (vector <pair <int, pair <int, int> > > :: iterator it = mc.begin(); it != mc.end() && use < n - 1; ++it) {
        int nod1 = it -> second.first, nod2 = it -> second.second;
        if (!tata[nod1] || !tata[nod2]) {
            msol.push_back(make_pair (nod1, nod2));
            use++;
            sol += it -> first;
            if (tata[nod1])
                tata[nod2] = nod2;
            else
                tata[nod1] = nod1;
            unite(nod1, nod2);
        }
    }
    fout << sol << "\n" << n - 1 << "\n";
    for (vector <pair <int, int> > :: iterator it = msol.begin(); it != msol.end(); ++it)
        fout << it -> first << " " << it -> second << "\n";
}