#include <bits/stdc++.h>

const int MAX_N = 200000;

using namespace std;

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

int n, m, s;
int tata[MAX_N], cnt[MAX_N];

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);

    cnt[y] += cnt[x];
    tata[x] = 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 <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        muchii.push_back({c, {a, b}});
    }

    for(int i = 1; i <= n; i++) {
        tata[i] = 0;
        cnt[i] = 1;
    }

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

    fout << s << '\n' << n - 1 << '\n';
    for(auto i : ans)
        fout << i.first << " " << i.second << '\n';

    return 0;
}