#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 father[NMAX], cost[NMAX], x[NMAX], y[NMAX], tree_cost, ind[NMAX];
vector<int> ans;
int n, m;

int find_(int x){
    if(x == father[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(int &n, int &m){
    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 solve(){
    for(int i = 1; i<=m; i++){
        if(find_(x[ind[i]]) != find_(y[ind[i]])){
            ans.push_back(ind[i]);
            tree_cost += cost[ind[i]];
            unite_(x[ind[i]], y[ind[i]]);
        }
    }
    g << tree_cost << '\n';
    g << n - 1<< '\n';
    for(int i = 0; i<ans.size(); i++){
        g << x[ans[i]] << ' ' << y[ans[i]] << '\n';
    }
}


int main(){
    read_data(n, m);
    solve();
    return 0;
}