#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int max_nodes = 200001;

struct Node {
    int parent;
    int parent_rank;
};

vector<Node> parent_vector(max_nodes);

bool sort_by_cost(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int find_root_node(int x) {
    if (parent_vector[x].parent == -1) {
        return x;
    }
    return parent_vector[x].parent = find_root_node(parent_vector[x].parent);
}

bool isCycle(int x, int y) {
    return find_root_node(x) == find_root_node(y);
}

void make_union(int x, int y) {
    int x_root_parent = find_root_node(x);
    int y_root_parent = find_root_node(y);
    if (parent_vector[x_root_parent].parent_rank > parent_vector[y_root_parent].parent_rank) {
        parent_vector[y_root_parent].parent = x;
    } else if (parent_vector[x_root_parent].parent_rank < parent_vector[y_root_parent].parent_rank) {
        parent_vector[x_root_parent].parent = y;
    } else {
        parent_vector[y_root_parent].parent = x;
        ++parent_vector[x_root_parent].parent_rank;
    }
}

int main() {
    int n, m;
    f >> n >> m;
    vector<vector<int>> edges;
    for (int i = 1; i <= m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        edges.push_back({x, y, cost});
    }
    sort(edges.begin(), edges.end(), sort_by_cost);

    for (int i = 1; i <= n; ++i) {
        parent_vector[i].parent = -1;
        parent_vector[i].parent_rank = 0;
    }
    /*for (int i = 0; i < m; ++i) {
        cout << edges[i][0] << " " << edges[i][1] << " " << edges[i][2] << "\n";
    }*/
    int nr_added_edges = 0;
    int total_cost = 0;
    vector<vector<int>> added_edges;
    for (int i = 0; i < m && nr_added_edges < n - 1; ++i) {
        int x = edges[i][0];
        int y = edges[i][1];
        int cost = edges[i][2];
        if (!isCycle(x, y)) {
            make_union(x, y);
            ++nr_added_edges;
            total_cost += cost;
            added_edges.push_back({x, y});
        }
    }
    g << total_cost << "\n";
    g << n - 1 << "\n";
    for (int i = 0; i < n - 1; ++i) {
        g << added_edges[i][0] << " " << added_edges[i][1] << "\n";
    }
    return 0;
}