#include <fstream>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define mp make_pair
using namespace std;

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

const int MAX = 200001;
int n, m, f[MAX], tcost;
vector <pair<int, pair<int, int>>> v;
vector <pair<int, int>> sol;

int find_root(int x){
    if(x != f[x])
        f[x] = find_root(f[x]);
    return f[x];
}

void unite(int x, int y){
    f[find_root(x)] = find_root(y);
}

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= n; i++)
        f[i] = i;

    for (int a, b, c; m; m--){
        fin >> a >> b >> c;
        v.push_back(mp(c, mp(a, b)));
    }
    sort(v.begin(), v.end());

    for(auto it: v){
        if (find_root(it.s.f) != find_root(it.s.s)){
            tcost += it.f;
            unite(it.s.f, it.s.s);
            sol.push_back(it.s);
        }
    }

    fout << tcost << '\n' << n - 1 << '\n';

    for (auto it: sol)
        fout << it.f << ' ' << it.s << '\n';

    return 0;
}