# include <fstream>
# include <algorithm>
# define DIM1 200010
# define DIM2 400010
# define a first.first
# define b first.second
# define c second
# define f first
# define s second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair <pair<int,int>,int> v[DIM2];
pair <int,int> sol[DIM1];
int t[DIM1],n,m,i,x,y,cost,ra,rb,nr,st;
int rad(int nod){
    while(t[nod]>0)
        nod=t[nod];
    return nod;
}
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        v[i].a=cost;
        v[i].b=x;
        v[i].c=y;
    }
    for(i=1;i<=n;i++)
        t[i]=-1;
    sort(v+1,v+m+1);
    for(i=1;i<=m&&nr<n-1;i++){
        ra=rad(v[i].b);
        rb=rad(v[i].c);
        if(ra!=rb){
            sol[++nr].f=v[i].b;
            sol[nr].s=v[i].c;
            st+=v[i].a;
            if(t[ra]<t[rb]){
                t[ra]+=t[rb];
                t[rb]=ra;
            }
            else{
                t[rb]+=t[ra];
                t[ra]=rb;
            }
        }
    }
    fout<<st<<"\n"<<nr<<"\n";
    for(i=1;i<=nr;i++)
        fout<<sol[i].f<<" "<<sol[i].s<<"\n";
    return 0;
}