#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <fstream>
using namespace std;

#define SIZE_N  (int)2e5 + 1

priority_queue<pair<int, pair<int, int>> > sorting;
vector<int> father(SIZE_N), degree(SIZE_N);
vector<int> n1, n2;

int find(int node) {
    int root;
    for (root = node; father[root] != root; root = father[root]);
    //compresioa drumurilor
    while (father[node] != node) {
        int auxNode = father[node];
        father[node] = root;
        node = auxNode;
    }
    return root;
}

void unite(int x, int y) {
    if (degree[x] > degree[y]) {
        father[y] = x;
    } else {
        father[x] = y;
    }
    if (degree[x] == degree[y]) {
        ++degree[y];
    }
}


int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, ans = 0;
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        degree[i] = 1;
    }
    for (int i = 1, x, y, cost; i <= m; ++i) {
        fin >> x >> y >> cost;
        sorting.push({-cost, {x, y}});
    }
    cout << '\n';
    while (!sorting.empty()) {
         // {    cost                         { x                                 y}}
         //-sorting.top().first      sorting.top().second.first        sorting.top().second.second
         int node1 = sorting.top().second.first, node2 = sorting.top().second.second;
         if (find(sorting.top().second.first) != find(sorting.top().second.second)) {
             unite(father[sorting.top().second.first], father[sorting.top().second.second]);
             ans += -sorting.top().first;
             n1.push_back(sorting.top().second.second);
             n2.push_back(sorting.top().second.first);
         }
         sorting.pop();
    }
    fout << ans << '\n';
    fout << n - 1 << '\n';
    for (int i = 0; i < n - 1; ++i) {
        fout << n1[i] << ' ' << n2[i] << '\n';
    }
}