#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n, m, x[400005], y[400005], c[400005], v[400005], t[200005];
int cost_min = 0;
vector<pair<int, int>> ans;

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

int grup (int k) {
    if (t[k] == k)
        return k;
    t[k] = grup (t[k]);
    return t[k];
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x[i] >> y[i] >> c[i];
        v[i] = i;
    }
    for (int i=1; i<=n; ++i)
        t[i] = i;
    sort (v+1, v+m+1, vrf);
    int k = 0;
    for (int i=1; i<=m && k<n-1; ++i) {
        int p, q;
        p = grup (x[v[i]]);   q = grup (y[v[i]]);
        if (p != q) {
            cost_min += c[v[i]];
            ++k;  ans.push_back (make_pair(x[v[i]], y[v[i]]));
            t[q] = p;
        }
    }
    g << cost_min << '\n' << k << '\n';
    for (auto z: ans)
        g << z.first << ' ' << z.second << '\n';
    return 0;
}