#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using piii = pair<int, pii>;

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

vector<int> t;
vector<piii> v;
vector<pii> APM;
int n, m;

inline int root(int x) {
    while (x != t[x])
        x = t[x];
    return x;
}

inline bool unite(int x, int y) {
    int tx = root(x);
    int ty = root(y);
    if (tx == ty)
        return 0;
    t[t[tx]] = t[ty];
    return 1;
}

inline void getAPM() {
    sort(v.begin(), v.end());
    int cost = 0;
    int c, x, y;
    for (const piii& node: v) {
        c = node.first;
        x = node.second.first;
        y = node.second.second;
        if (unite(x, y)) {
            cost += c;
            APM.push_back({x, y});
        }
    }
    fout << cost << '\n' << APM.size() << '\n';
    for (const pii& node: APM)
        fout << node.first << ' ' << node.second << '\n';
}

int main()
{
    fin >> n >> m;
    t.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        t[i] = i;
    for (int c, x, y; m; --m) {
        fin >> x >> y >> c;
        v.push_back({c, {x, y}});
    }
    getAPM();
    return 0;
}