#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int NMAX = 2e5 + 10, mod = 1e9 + 7;
int n, p[NMAX], m;

int find(int x) {
    if (p[x] == x)
        return x;
    return (p[x] = find(p[x]));
}

void unite(int x, int y) {
    p[find(x)] = find(y);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin >> n >> m;
    vector<edge> a(m);
    for (int i = 0; i < m; i++)
        cin >> a[i].x >> a[i].y >> a[i].cost;
    sort(a.begin(), a.end(), [](edge A, edge B) {
       return A.cost < B.cost;
    });
    for (int i = 1; i <= n; i++)
        p[i] = i;

    int sum = 0;
    vector<pair<int, int>> ans;
    for (auto it: a)
        if (find(it.x) != find(it.y)) {
            unite(it.x, it.y);
            sum += it.cost;
            ans.emplace_back(it.x, it.y);
        }

    cout << sum << '\n' << ans.size() << '\n';
    for (auto it: ans)
        cout << it.first << ' ' << it.second << '\n';
}