#include <bits/stdc++.h>

using namespace std;

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

struct muchie{
    int x, y, cost;
};

int n, m, c;
vector<muchie> v;
vector<int> comp;
vector<muchie> apm;

bool cmp(muchie a, muchie b){
    return a.cost<b.cost;
}

int GetRoot(int x){
    /*if(comp[x]==x){
        return x;
    }else{
        comp[x]=GetRoot(comp[x]);
    }*/
    return comp[x]==x?x:(comp[x]=GetRoot(comp[x]));
}

void Unite(int x, int y){
    comp[GetRoot(x)]=GetRoot(y);
}

void kruskal(){
    int x=0, y=0;
    for(int i=0; i<m; i++){
        x=comp[v[i].x];
        y=comp[v[i].y];
        if(GetRoot(x)!=GetRoot(y)){
            apm.push_back(v[i]);
            c+=v[i].cost;
            Unite(x, y);
        }
        if(apm.size()==n-1){
            break;
        }
    }
}

int main()
{
    in>>n>>m;
    muchie M;
    comp.resize(n+1);
    for(int i=1; i<=n; i++){
        comp[i]=i;
    }
    for(int i=1; i<=m; i++){
        in>>M.x>>M.y>>M.cost;
        v.push_back(M);
    }
    sort(v.begin(), v.end(), cmp);
    kruskal();
    out<<c<<'\n';
    out<<apm.size()<<'\n';
    for(auto el:apm){
        out<<el.x<<" "<<el.y<<'\n';
    }
    return 0;
}