#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int mmax = 400000, nmax = 200000;

struct muchie{
    int x, y, c;
}v[mmax + 5];
vector <pair <int, int>> sol;
int n, m, cost, tt[nmax + 5], level[nmax + 5];

void Read(){
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].c;
}

int Compare(muchie a, muchie b){
    return a.c < b.c;
}

int Rad(int nod){
    while (tt[nod])
        nod = tt[nod];
    return nod;
}

void Solve(){
    sort(v + 1, v + m + 1, Compare);
    for (int i = 1; i <= m; i++){
        int r1 = Rad(v[i].x), r2 = Rad(v[i].y);
        if (r1 != r2){
            cost += v[i].c;
            sol.push_back(make_pair(v[i].x, v[i].y));
            if (level[r1] > level[r2])
                swap(r1, r2);
            tt[r1] = r2;
            level[r2] = max(level[r2], level[r1] + 1);
        }
    }
}

void Print(){
    fout << cost << '\n' << n - 1 << '\n';
    for (auto i : sol)
        fout << i.first << ' ' << i.second << '\n';
}

int main(){
    Read();
    Solve();
    Print();
    return 0;
}