#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, int &h) {
    h = 0;
    while (t[k] != k) {
        k = t[k];
        ++h;
    }
    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, hp = 0, hq = 0;
        p = grup (x[ind[i]], hp);
        q = grup (y[ind[i]], hq);

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