#include <bits/stdc++.h>

using namespace std;
const int nmax = 200005;

struct geani {
    int x; int y; int val;
};

int n, m, cnt, cost, parent[nmax];
vector<geani> v;
vector<pair<int, int>> ans;

int get_root(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = get_root(parent[x]);
}

void unire(int x, int y) {
    int a = get_root(x);
    int b = get_root(y);
    parent[a] = parent[b];
}

inline bool cmp(geani &a, geani &b) {
    return a.val < b.val;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    v.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> v[i].x >> v[i].y >> v[i].val;
    }
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < m; i++) {
        if (get_root(v[i].x) != get_root(v[i].y)) {
            cost += v[i].val;
            cnt++;
            unire(v[i].x, v[i].y);
            ans.push_back({v[i].x, v[i].y});
        }
        if (cnt == n - 1)
            break;
    }
    cout << cost << '\n' << n - 1 << '\n';
    for (auto geani : ans)
        cout << geani.first << ' ' << geani.second << '\n';
    return 0;
}