#include <fstream>
#include <set>
#include <map>
using namespace std;

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

set <pair <int, pair<int, int>>> muchii;
map <int, int> tata;

void citire(int &n, int &m) {
    in >> n >> m;

    int x, y, c;
    for (int i = 0; i < m; i ++) {
        in >> x >> y >> c;
        muchii.insert({c, {x, y}});
    }
}

void createTata(int n) {
    for (int i = 1; i <= n; i ++) {
        tata.insert({i, i});
    }
}

int findTata(int x) {
    while(tata[x] != tata[tata[x]]) {
        tata[x] = findTata(tata[x]);
    }
    return tata[x];
}

int main() {
    int n, m;
    citire(n, m);
    createTata(n);

    int cost = 0;
    for (auto i = muchii.begin(); i != muchii.end();) {
        int x = i->second.first, y = i->second.second;
        if (findTata(x) != findTata(y)) {
            tata[tata[y]] = tata[x];
            cost += i->first;
            i ++;
        } else {
            i = muchii.erase(i);
        }
    }

    out << cost << '\n' << muchii.size() << '\n';
    for (auto i = muchii.begin(); i != muchii.end(); i ++) {
        out << i->second.first << " " << i->second.second << '\n';
    }

    return 0;
}