#include <bits/stdc++.h>
using namespace std;

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

int n, m, t[200001];
edge v[400001];

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

bool comp(edge a, edge b) {
    return a.cost < b.cost;
}

int rad(int node) {
    if (t[node] == node) {
        return node;
    }
    return t[node] = rad(t[node]);
}

void kruskal() {
    sort(v + 1, v + m + 1, comp);
    for (int i = 1; i <= m; ++i) {
        int r1 = rad(v[i].x);
        int r2 = rad(v[i].y);
        if (r1 != r2) {
            t[r2] = r1;
            totalCost += v[i].cost;
            ans.push_back({v[i].x, v[i].y});
        }
    }
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        t[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> v[i].x >> v[i].y >> v[i].cost;
    }
    kruskal();
    cout << totalCost << "\n" << ans.size() << "\n";
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i].first << " " << ans[i].second << "\n";
    }
}