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

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

vector<tuple<int, int, int>> muchii;
vector<int> parent;
vector<int> sz;
vector<pair<int, int>> ans;
int n, m;

int find_parent(int node) {
    if (node == parent[node]) return node;
    parent[node] = find_parent(parent[node]);
    return parent[node];
}

void union_sets(int node1, int node2) {
    node1 = find_parent(node1);
    node2 = find_parent(node2);
    if (node1 != node2) {
        if (sz[node1] < sz[node2]) swap(node1, node2);
        parent[node2] = node1;
        sz[node1] += sz[node2];
    }
}

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

int main() {
    cin >> n >> m;
    parent.resize(n + 2);
    for (int i = 1 ; i <= n ; ++i) parent[i] = i;
    sz.resize(n + 2, 1);
    for (int i = 0 ; i < m ; ++i) {
        int src, dest, cost;
        cin >> src >> dest >> cost;
        muchii.push_back({src, dest, cost});
    }
    sort(muchii.begin(), muchii.end(), compare);
    int treeCost = 0, edgeCount = 0;
    for (int i = 0 ; i < m ; ++i) {
        int node1, node2, cost;
        tie(node1, node2, cost) = muchii[i];
        if (find_parent(node1) != find_parent(node2)) {
            union_sets(node1, node2);
            ans.push_back({node1, node2});
            treeCost += cost;
            edgeCount++;
        }
    }
    cout << treeCost << "\n" << edgeCount << "\n";
    for (pair<int,int> edge : ans) {
        cout << edge.first << " " << edge.second << "\n";
    }
    return 0;
}