#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

#define NMAX 200000
#define MMAX 400000

int n, m;
pair<int, pair<int, int>> muchii[MMAX + 1];
int t[MMAX + 1], card[NMAX + 1];
int sol[MMAX + 1], cost;

void read() {
    cin >> n >> m;
    for (int i = 0; i < m; i += 1) {
        int x, y, c;
        cin >> x >> y >> c;
        muchii[i] = make_pair(c, make_pair(x, y));
    }
}

void init() {
    sort(muchii, muchii + m);
    for (int i = 1; i <= n; i += 1) {
        card[i] = 1;
    }
}

int rad(int x) {
    while (t[x] != 0) {
        x = t[x];
    }
    return x;
}

void solve() {
    int s = 0;
    for (int i = 0; i < m && s < n - 1; i += 1) {
        int c = muchii[i].first;
        int x = rad(muchii[i].second.first);
        int y = rad(muchii[i].second.second);
        if (x == y) {
            continue;
        }

        if (card[x] < card[y]) {
            swap(x, y);
        }

        cost += c;
        t[y] = x;
        card[x] += card[y];
        sol[s] = i;
        s += 1;
    }
}

void afis() {
    cout << cost << '\n';
    cout << n-1 << '\n';
    for (int i = 0; i < n-1; i += 1) {
        pair<int, int> muchie = muchii[sol[i]].second;
        cout << muchie.first << ' ' << muchie.second << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    read();
    init();
    solve();
    afis();

    return 0;
}