#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int MAXN = 200000;

int n, m;
vector<pair<int, pair<int, int>>> edges;
int parent[MAXN + 1];
vector<pair<int, int>> result;

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

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

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back({c, {x, y}});
    }

    sort(edges.begin(), edges.end());

    for (int i = 1; i <= n; i++)
        parent[i] = i;

    long long total_cost = 0;
    int edges_used = 0;

    for (auto &edge : edges) {
        int cost = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (find(u) != find(v)) {
            unite(u, v);
            total_cost += cost;
            result.push_back({u, v});
            edges_used++;
            if (edges_used == n - 1) break;
        }
    }

    fout << total_cost << "\n";
    fout << edges_used << "\n";
    for (auto &e : result)
        fout << e.first << " " << e.second << "\n";

    fin.close();
    fout.close();
    return 0;
}