#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int tata[400001],n,m,i,j,k,S,r1,r2;
struct nr{
    int x;
    int y;
    int c;
    int viz;
}v[400001];
int cmp(nr a, nr b){

        return a.c<b.c;
}
int Tata(int x){
    while(tata[x]>0)
        x=tata[x];
    return x;
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>v[i].x>>v[i].y>>v[i].c;
    }
    for(i=1;i<=n;i++)
        tata[i]=-1;
    sort(v+1,v+m+1,cmp);
    k=0; S=0;
    for(i=1;i<=m&&k<n;i++){
        r1=Tata(v[i].x);
        r2=Tata(v[i].y);
        if(r1!=r2){
            v[i].viz=1;
            S=S+v[i].c;
            k++;
            if(tata[r1]<tata[r2]){
                tata[r1]+=tata[r2];
                tata[r2]=r1;
            }
            else{
                tata[r2]+=tata[r1];
                tata[r1]=r2;
            }
        }
    }
    cout<<S<<"\n"<<k<<"\n";
    for(i=1;i<=m;i++)
        if(v[i].viz==1){
            cout<<v[i].x<<" "<<v[i].y<<"\n";
    }
    return 0;
}