#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, w[200005], rx, ry, leg, sol, k;
pair <int, pair<int, int> > v[400005], xsol[400005];

int rad(int p){
    while(w[p] > 0){
        p = w[p];
    }
    return p;
}

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= n; i++){
        w[i] = -1;
    }
    for(int i = 1; i <= m; i++){
        fin>>v[i].second.first>>v[i].second.second>>v[i].first;
    }
    sort(v + 1, v + m + 1);
    for(int i = 1; i <= m; i++){
        rx = rad(v[i].second.first);
        ry = rad(v[i].second.second);
        if(rx != ry){
            leg++;
            sol += v[i].first;
            if(rx < ry){
                w[rx] = w[ry];
                w[ry] = rx;
            }
            else{
                w[ry] = w[rx];
                w[rx] = ry;
            }
            k++;
            xsol[k].second.first = v[i].second.first;
            xsol[k].second.second = v[i].second.second;
        }
    }
    fout<<sol<<"\n"<<leg<<"\n";
    for(int i = 1; i <= k; i++){
        fout<<xsol[i].second.first<<" "<<xsol[i].second.second<<"\n";
    }
    return 0;
}