#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax=200000, mmax=400000, cmax=1000;

struct str3{
    int x,y,z;
};

struct cmp{
    bool operator()(str3 x, str3 y){
        return x.z<y.z;
    }
};

str3 g[mmax+1];

int r[nmax+1], vsol[nmax][2];

void update(int x){
    int i=x;
    while(r[i]!=r[r[i]]){
        i=r[i];
    }
    while(r[x]!=r[r[x]]){
        int j=r[x];
        r[x]=r[i];
        x=j;
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>g[i].x>>g[i].y>>g[i].z;
    }
    sort(g+1,g+m+1,cmp());
    for(int i=1;i<=n;i++){
        r[i]=i;
    }
    int nsol=0,sol=0;
    for(int i=1;i<=m;i++){
        int x=g[i].x;
        int y=g[i].y;
        update(x);
        update(y);
        if(r[x]!=r[y]){
            sol+=g[i].z;
            nsol++;
            vsol[nsol][0]=x;
            vsol[nsol][1]=y;
            r[r[y]]=r[x];
            r[y]=r[x];
        }
    }
    fout<<sol<<"\n"<<n-1<<"\n";
    for(int i=1;i<=n-1;i++){
        fout<<vsol[i][0]<<" "<<vsol[i][1]<<"\n";
    }
    return 0;
}