#include<fstream>
#include<algorithm>
#include<cstring>
#define C first
#define X second.first
#define Y second.second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i;
int t[200005];
pair<int,pair<int,int> >p[400005];
pair<int,int> sol[200005];
int a,b,sum;
int rad(int x){
    if(t[x]>0){
        return rad(t[x]);
    }
    return x;
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>p[i].X>>p[i].Y>>p[i].C;
    }
    sort(p+1,p+m+1);
    memset(t,-1,sizeof(t));
    int k=0;
    for(i=1;i<=m;i++){
        a=rad( p[i].X );
        b=rad( p[i].Y );
        if(a!=b){
            if(t[a]<t[b]){
                t[a]+=t[b];
                t[b]=a;
            }else{
                t[b]+=t[a];
                t[a]=b;
            }
            sol[++k].first=p[i].X;
            sol[k].second=p[i].Y;
            sum+=p[i].C;
        }
    }
    fout<<sum<<"\n";
    fout<<k<<"\n";
    for(i=1;i<=k;i++){
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
    return 0;
}