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

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

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

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

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }
    sort (ind+1, ind+m+1, srt);

    for (int i=1; i<=n; ++i)
        t[i] = i;

    int k = 0;
    for (int i=1; i<=m && k<n-1; ++i) {
        int p, q;
        p = grup (x[ind[i]]);
        q = grup (y[ind[i]]);

        if (p != q) {
            cost_min += c[ind[i]];
            t[p] = q;
            ans.push_back (make_pair (x[ind[i]], y[ind[i]]));
            ++k;
        }
    }
    g << cost_min << '\n' << k << '\n';
    for (auto x: ans)
        g << x.first << ' ' << x.second << '\n';
    return 0;
}