#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, m;
int costTotal;
vector<vector<int>> v;
vector<int> tata;

int root(int x){
    if (tata[x] != x) {
        tata[x] = root(tata[x]);
        return tata[x];
    }
    return x;
}


vector<pair<int, int>> Kruskal(){
    vector<pair<int, int>> sol;
    costTotal = 0;
    for (int i = 1;  i <= m; ++i) {
        if(root(v[i][1]) != root(v[i][2])) {
            tata[root(v[i][2])] = v[i][1];
            sol.push_back({v[i][2], v[i][1]});
            costTotal += v[i][0];
        }
    }
    return sol;
}

int main() {
    in >> n >> m;
    v.resize(m+1);
    tata.resize(n+1);
    for(int i = 1; i <= n; ++i)
        tata[i] = i;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        in >> x >> y >> c;
        v[i].push_back(c);
        v[i].push_back(x);
        v[i].push_back(y);
    }
    sort(v.begin(), v.end());
    vector<pair<int, int>> sol = Kruskal();
    out << costTotal << '\n' << sol.size() << '\n';
    for (auto x : sol) {
        out << x.first << ' ' << x.second << '\n';
    }
    return 0;
}