#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct edge{
    int x, y, c;
};

edge v[400005];

int n, m, p[200005], h[200005];
int cmin = 0;
vector<pair<int, int>> ans;

int Find(int x) {
    int r = x;
    while (p[r] != r)
        r = p[r];
    while (x != r) {
        int aux = p[x];
        p[x] = r;
        x = aux;
    }

    return r;
}

void Unite(int x, int y) {
    int rx = Find(x);
    int ry = Find(y);

    if (h[rx] < h[ry]) {
        p[rx] = ry;
    } else {
        p[ry] = rx;
    }

    if (h[rx] == h[ry])
        h[rx]++;
}

void kruskal() {
    for (int i = 1; i <= n; i++)
        p[i] = i;

    int k = 0;

    for (int i = 1; i <= m && k < n - 1; i++) {
        int rx = Find(v[i].x);
        int ry = Find(v[i].y);
        if (rx != ry) {
            cmin += v[i].c;
            Unite(v[i].x, v[i].y);
            k++;
            ans.push_back({v[i].x, v[i].y});
        }
    }

}

int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> v[i].x >> v[i].y >> v[i].c;
    }

    sort(v + 1, v + m + 1, [](const edge& a, const edge& b) {
            return a.c < b.c;
         });

    kruskal();

    out << cmin << '\n' << n - 1 << '\n';
    for (auto it : ans)
        out << it.first << " " << it.second << '\n';

    return 0;
}