#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
#define NMAX 200005
using namespace std;

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

int x[NMAX], y[NMAX], father[NMAX], cost[NMAX], ind[NMAX];
vector<int> ans;
int n, m, cost_sol;

int find_(int x){
    if(father[x] == x){
        return x;
    }
    father[x] = find_(father[x]);
    return father[x];
}

void unite_(int x, int y){
    father[find_(y)] = find_(x);
}

bool cmp(int x, int y){
    return cost[x] < cost[y];
}

void read_data(){
    f >> n >> m;
    for(int i = 1; i<=m; i++){
        f >> x[i] >> y[i] >> cost[i];
        ind[i] = i;
    }
    for(int i = 1; i<=n; i++){
        father[i] = i;
    }
    sort(ind + 1, ind + m + 1, cmp);
}

void make_apm(){
    for(int i = 1; i<=m; i++){
        if(find_(x[ind[i]]) != find_(y[ind[i]])){
            ans.pb(ind[i]);
            cost_sol += cost[ind[i]];
            unite_(x[ind[i]], y[ind[i]]);
        }
    }
}

void print_sol(){
    g << cost_sol << '\n' << n - 1 << '\n';
    for(int i = 0; i<ans.size(); i++){
        g << x[ans[i]] << ' ' << y[ans[i]] << '\n';
    }
}

int main(){
    read_data();
    make_apm();
    print_sol();
    return 0;
}