#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>

using namespace std;

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

constexpr int INF = 2e9;
using Graph = vector<vector<pair<int, int>>>;

struct MinimumSpanningTree {
    vector<pair<int, int>> edges;
    int cost;

    MinimumSpanningTree()
        : edges(), cost() {}
};

MinimumSpanningTree minimum_spanning_tree(const Graph &graph) {
    MinimumSpanningTree mst;

    vector<bool> visited(graph.size(), false);
    vector<int> prev(graph.size(), -1);
    vector<int> min_cost(graph.size(), INF);
    set<pair<int, int>> pq;

    for (int i = 0; i < (int)graph.size(); ++i)
        if (!visited[i]) {
            pq.emplace(0, 0);
            while (!pq.empty()) {
                const auto[cost, node] = *pq.begin();
                pq.erase(pq.begin());
                visited[node] = true;
                if (prev[node] != -1) {
                    mst.edges.emplace_back(prev[node], node);
                    mst.cost += cost;
                }


                for (const auto[adj_cost, adj_node] : graph[node])
                    if (!visited[adj_node] && min_cost[adj_node] > adj_cost) {
                        pq.erase(make_pair(min_cost[adj_node], adj_node));
                        min_cost[adj_node] = adj_cost;
                        prev[adj_node] = node;
                        pq.emplace(adj_cost, adj_node);
                    }
            }
        }

    return mst;
}

int main() {
    int V, E;
    fin >> V >> E;
    Graph graph(V);
    for (int i = 0; i < E; ++i) {
        int node1, node2, cost;
        fin >> node1 >> node2 >> cost;
        --node1, --node2;
        graph[node1].emplace_back(cost, node2);
        graph[node2].emplace_back(cost, node1);
    }

    MinimumSpanningTree mst = minimum_spanning_tree(graph);

    fout << mst.cost << '\n' << mst.edges.size() << '\n';
    for (const auto[node1, node2] : mst.edges)
        fout << node1 + 1 << ' ' << node2 + 1 << '\n';

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