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

using namespace std;

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

constexpr int LIM = 2e5 + 1;

struct Solution {
    vector<pair<int, int>> edges;
    int cost = 0;
};

int N, M, i, node1, node2, weight;
vector<tuple<int, int, int>> edges;
int disjoint[LIM];

bool compare(
    const tuple<int, int, int>& edge1,
    const tuple<int, int, int>& edge2
) {
    return get<2>(edge1) < get<2>(edge2);
}

static inline int get_root(int node) {
    int aux = node;
    while (disjoint[node] > 0)
        node = disjoint[node];
    int root = node;
    node = aux;
    while (node != root) {
        aux = disjoint[node];
        disjoint[node] = root;
        node = aux;
    }
    return root;
}

static inline void join(int node1, int node2) {
    int root1 = get_root(node1);
    int root2 = get_root(node2);
    if (root1 == root2) return;

    if (disjoint[root1] <= disjoint[root2]) {
        disjoint[root1] += disjoint[root2];
        disjoint[root2] = root1;
    } else {
        disjoint[root2] += disjoint[root1];
        disjoint[root1] = root2;
    }
}

// Algoritmul lui Kruskal
static inline Solution minimum_spanning_tree() {
    Solution sol;

    for (i = 1; i <= N; ++i)
        disjoint[i] = -1;

    sort(edges.begin(), edges.end(), compare);
    for (const auto[node1, node2, weight] : edges) {
        if (get_root(node1) != get_root(node2)) {
            sol.cost += weight;
            sol.edges.emplace_back(node1, node2);
            join(node1, node2);
        }
    }

    return sol;
}

int main() {
    fin >> N >> M;
    for (i = 1; i <= M; ++i) {
        fin >> node1 >> node2 >> weight;
        edges.emplace_back(node1, node2, weight);
        edges.emplace_back(node2, node1, weight);
    }

    Solution sol = minimum_spanning_tree();

    fout << sol.cost << '\n' << sol.edges.size() << '\n';
    for (const pair<int, int>& edge : sol.edges)
        fout << edge.first << ' ' << edge.second << '\n';

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