#include <fstream>
#include <algorithm>
#include <vector>

const int MAX_N = 100000;

using namespace std;

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

int n, m;
int tata[MAX_N + 5], cnt[MAX_N + 5];
long long s;

vector<pair<int, pair<int, int>>> muchii;
vector<pair<int, int>> ans;

int rad(int x) {
    if(tata[x] == 0)
        return x;
    else tata[x] = rad(tata[x]);
    return tata[x];
}

void join(int x, int y) {
    x = rad(x);
    y = rad(y);

    if(cnt[x] > cnt[y])
        swap(x, y);

    tata[x] = y;
    cnt[y] += cnt[x];
}

bool query(int x, int y) {
    return (rad(x) == rad(y));
}

void apm() {
    for(int i = 0; i < muchii.size(); i++) {
        int a = muchii[i].second.first, b = muchii[i].second.second;

        if(rad(a) == rad(b))
            continue;

        s += muchii[i].first;
        ans.push_back({a, b});
        join(a, b);
    }
}
int main() {
    fin >> n >> m;

    for(int i = 1; i <= n; i++) {
        tata[i] = 0;
        cnt[i] = 1;
    }
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        muchii.push_back({c, {a, b}});
    }

    sort(muchii.begin(), muchii.end());

    apm();

    fout << s << '\n' << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i++)
        fout << ans[i].first << ' ' << ans[i].second << '\n';

    return 0;
}