#include <cstdint>
#include <fstream>
#include <functional>
#include <vector>
#include <queue>

#define MAX_N 200005

struct Edge {
    int to, cost;
    Edge(int to, int cost) : to{to}, cost{cost} {}
};

struct PQEdge {
    int node, cost;

    PQEdge(int node, int cost) : node{node}, cost{cost} {}

    bool operator>(const PQEdge& other) const
    {
        return cost > other.cost;
    }
};

struct MSTEdge {
    int x, y;
};

std::vector<Edge> adj[MAX_N];
bool visited[MAX_N];

int main() {
    std::ifstream fin("apm.in");
    std::ofstream fout("apm.out");

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

    for (int i = 0; i < m; i++) {
        int u, v, cost;
        fin >> u >> v >> cost;

        adj[u].push_back(Edge(v, cost));
        adj[v].push_back(Edge(u, cost));
    }

    std::priority_queue<PQEdge, std::vector<PQEdge>, std::greater<PQEdge>> pq;
    std::vector<MSTEdge> mst_edges;
    intmax_t total_cost = 0;

    pq.push(PQEdge(1, 0));

    while (!pq.empty()) {
        auto current = pq.top();
        pq.pop();

        if (visited[current.node]) {
            continue;
        }

        visited[current.node] = true;
        total_cost += current.cost;

        for (auto e : adj[current.node]) {
            if (!visited[e.to]) {
                pq.push(PQEdge(e.to, e.cost));
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (auto e : adj[i]) {
            if (visited[i] && visited[e.to]) {
                mst_edges.push_back({i, e.to});
                if (mst_edges.size() == n - 1) {
                    break;
                }
            }

            if (mst_edges.size() == n - 1) {
                break;
            }
        }
    }

    fout << total_cost << "\n";
    fout << mst_edges.size() << "\n";
    for (auto e : mst_edges) {
        fout << e.x << " " << e.y << "\n";
    }
}