#include<fstream>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define BN 200005
#define BM 2*BN
typedef pair<int,int> per;
#define it vector<per>::iterator
int n,m,cf;
struct s{
    int x,y,c;
};
s mc[BM];
int rad[BN];
vector<per>sol;
bool cmp(const s &a, const s &b){
    return a.c<b.c;
}
int un (int crt){
    if(rad[crt]==crt)return crt;
    rad[crt]=un(rad[crt]);
    return rad[crt];
}
int main (){
    int i;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;++i)f>>mc[i].x>>mc[i].y>>mc[i].c;
    sort(mc+1,mc+m+1,cmp);
    for(i=1;i<=n;++i)rad[i]=i;
    for(i=1;i<=m;++i){
        if(un(mc[i].x)!=un(mc[i].y)){
            rad[un(mc[i].y)]=un(mc[i].x);
            sol.push_back(make_pair(mc[i].x,mc[i].y));
            cf+=mc[i].c;
        }
    }
    g<<cf<<'\n'<<n-1<<'\n';
    for(it j=sol.begin();j!=sol.end();++j)g<<j->first<<' '<<j->second<<'\n';
    return 0;
}