#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,j,a,b,c,v[222222],d,val;
struct qwerty{
    int in,out;
    short val;
}x[444444];
struct solutie{
    int in,out;
}z[444444];
bool cum(qwerty a,qwerty b){
    if(a.val==b.val){
        if(a.in==b.in)
            return a.out<b.out;
        return a.in<b.in;
    }
    return a.val<b.val;
}
int rad(int x){
    if(x!=v[x])
        v[x]=rad(v[x]);
    return v[x];
}
void unire(int a,int b){
    v[v[a]]=v[b];
}
int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++)
        v[i]=i;
    for(i=1;i<=m;i++)
        fin>>x[i].in>>x[i].out>>x[i].val;
    sort(x+1,x+1+m,cum);
    for(i=1;i<=m&&d<n;i++){
        if(rad(x[i].in)!=rad(x[i].out)){
            unire(x[i].in,x[i].out);
            val+=x[i].val;
            z[++d].in=x[i].in;
            z[d].out=x[i].out;
        }
    }
    fout<<val<<'\n'<<d<<'\n';
    for(i=1;i<=d;i++)
        fout<<z[i].out<<' '<<z[i].in<<'\n';
    return 0;
}