#include <bits/stdc++.h>
using namespace std;

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

const int mxN = 2e5 + 5;

int n, m, cost, tata[mxN], rang[mxN];
set<pair<int, pair<int, int>>> s;
vector<pair<int, int>> rez;

int radacina(int x) {
    int Radacina;
    for (Radacina = x; Radacina != tata[Radacina]; Radacina = tata[Radacina]);
    while (x != tata[x]) {
        int aux = x;
        tata[x] = Radacina;
         x = tata[aux];
    }
    return Radacina;
}

void reuniune(int x, int y) {
    if (rang[x] > rang[y]) {
        tata[y] = x;
        rang[x] += rang[y];
    } else {
        tata[x] = y;
        rang[y] += rang[x];
    }
}

int main() {
    ios::sync_with_stdio(false), fin.tie(nullptr), fout.tie(nullptr);
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        tata[i] = i;
        rang[i] = i;
    }
    while (m--) {
        int x, y, z; fin >> x >> y >> z;
        s.insert({z, {x, y}});
    }
    while (!s.empty()) {
        int node1 = s.begin()->second.first;
        int node2 = s.begin()->second.second;
        int new_cost = s.begin()->first;
        s.erase(s.begin());
        if (radacina(node1) == radacina(node2)) continue;
        cost += new_cost;
        rez.push_back({node1, node2});
        reuniune(radacina(node1), radacina(node2));
    }
    fout << cost << '\n';
    fout << rez.size() << '\n';
    for (auto elem : rez) {
        fout << elem.first << " " << elem.second << '\n';
    }
    return 0;
}