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

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

vector<vector<pair<int,int>>> adj;
vector<bool> used;
vector<pair<int,int>> apm;

/* Algoritmul lui Prim */
long long prim(int n) {
    priority_queue<
        tuple<int,int,int>,              // (cost, nod, parinte)
        vector<tuple<int,int,int>>,
        greater<tuple<int,int,int>>
    > pq;

    used.assign(n + 1, false);
    long long total_cost = 0;

    // pornim din nodul 1 (graful este conex)
    pq.push({0, 1, 0});

    while (!pq.empty() && apm.size() < n - 1) {
        auto [cost, node, parent] = pq.top();
        pq.pop();

        if (used[node]) continue;

        used[node] = true;
        total_cost += cost;

        if (parent != 0)
            apm.emplace_back(parent, node);

        for (auto &[to, w] : adj[node]) {
            if (!used[to])
                pq.push({w, to, node});
        }
    }

    return total_cost;
}

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

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

    adj.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    long long cost = prim(n);

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

    return 0;
}