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

struct Edge {
    int u, v;
    long long w;
};

int N;
vector<vector<pair<int,long long>>> graph;
vector<bool> visited;
vector<int> parent;
vector<long long> parent_weight;
vector<Edge> mst_edges;
long long total_cost = 0;

void init_graph(int n) {
    N = n;
    graph.assign(N+1, {});
    visited.assign(N+1, false);
    parent.assign(N+1, -1);
    parent_weight.assign(N+1, 0);
    mst_edges.clear();
    total_cost = 0;
}

void add_edge(int u, int v, long long w) {
    if (u < 1 || u > N || v < 1 || v > N) return;
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

void prim_from(int start) {
    if (visited[start]) return;
    priority_queue< tuple<long long,int,int>, vector<tuple<long long,int,int>>, greater<tuple<long long,int,int>> > pq;
    pq.push({0, start, -1});

    while (!pq.empty()) {
        auto [w, node, par] = pq.top(); pq.pop();
        if (visited[node]) continue;
        visited[node] = true;
        parent[node] = par;
        parent_weight[node] = w;
        if (par != -1) {
            mst_edges.push_back(Edge{par, node, w});
            total_cost += w;
        }
        for (auto &pr : graph[node]) {
            int nbr = pr.first;
            long long wt = pr.second;
            if (!visited[nbr]) pq.push({wt, nbr, node});
        }
    }
}

void prim_full() {
    fill(visited.begin(), visited.end(), false);
    mst_edges.clear();
    total_cost = 0;
    fill(parent.begin(), parent.end(), -1);
    fill(parent_weight.begin(), parent_weight.end(), 0);

    for (int v = 1; v <= N; ++v)
        if (!visited[v])
            prim_from(v);
}

int main() {
    int M;
    if (!(cin >> N >> M)) return 0;
    init_graph(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    prim_full();

    cout << total_cost << "\n";
    cout << mst_edges.size() << "\n";
    for (auto &e : mst_edges) {
        cout << e.u << " " << e.v << "\n";
    }
    return 0;
}