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

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

struct Edge {
    int u, v, cost;
};

vector<int> parent;
vector<Edge> edges;
vector<pair<int,int>> apm;

/* Gaseste reprezentantul multimii */
int find_set(int x) {
    if (parent[x] < 0)
        return x;
    return parent[x] = find_set(parent[x]);
}

/* Uneste doua multimi */
bool unite(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return false;

    if (parent[a] > parent[b])
        swap(a, b);

    parent[a] += parent[b];
    parent[b] = a;
    return true;
}

/* Algoritmul Kruskal */
long long kruskal(int n) {
    sort(edges.begin(), edges.end(),
         [](const Edge& a, const Edge& b) {
             return a.cost < b.cost;
         });

    parent.assign(n + 1, -1);
    long long total_cost = 0;

    for (const auto& e : edges) {
        if (unite(e.u, e.v)) {
            total_cost += e.cost;
            apm.emplace_back(e.u, e.v);
            if ((int)apm.size() == n - 1)
                break;
        }
    }
    return total_cost;
}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    int n, m;
    fin >> n >> m;

    edges.resize(m);
    for (int i = 0; i < m; i++) {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

    long long cost = kruskal(n);

    fout << cost << "\n";
    fout << apm.size() << "\n";
    for (auto &e : apm)
        fout << e.first << " " << e.second << "\n";

    return 0;
}