#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, x, y, val,ans;
struct tupla {
    int x, y, val;
    tupla(int a, int b, int c) : x(a), y(b), val(c) {};
    bool operator <(const tupla& any) const {
        return this->val < any.val;
    }
};
vector <tupla> edge;
vector <pair<int, int>> rasp;
vector <int> t;
int root(int x) {
    if (t[x] == x) return x;
    int aux = root(t[x]);
    t[x] = aux;
    return t[x];
}
void uneste(int a, int b) {
    t[root(a)] = root(b);
}
int main()
{ 
    fin >> n >> m;
    t = vector <int>(n + 5, 0);
    for (int i = 1; i <= n; ++i) t[i] = i;
    for (int i = 1; i <= m;++i) fin >> x >> y >> val, edge.push_back(tupla(x, y, val));
    sort(edge.begin(), edge.end());
    for (auto it : edge) {
        if (root(it.x) != root(it.y)) {
            ans += it.val;
            uneste(it.x, it.y),rasp.push_back({it.x,it.y});
        }
    }
    fout << ans<<'\n'<< n - 1 << '\n';
    for (auto it : rasp) fout << it.first << " " << it.second << '\n';
    return 0;
}