# include <fstream>
# include <algorithm>
# define DIM 400010
# define cost first.first
# define x first.second
# define y second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair<pair<int,int>,int> sor[DIM],sol[DIM];
int t[DIM],n,m,i,ra,rb,a,b,val,k,Cost;
int rad(int X){
    int Y=X;
    while(t[X]>0)
        X=t[X];
    while(t[Y]>0){
        int aux=Y;
        Y=t[Y];
        t[aux]=X;
    }
    return X;
}
int main () {
    fin>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=-1;
    for(i=1;i<=m;i++)
        fin>>sor[i].x>>sor[i].y>>sor[i].cost;
    sort(sor+1,sor+m+1);
    for(i=1;i<=m;i++){
        a=sor[i].x;
        b=sor[i].y;
        Cost=sor[i].cost;
        ra=rad(a);
        rb=rad(b);
        if(ra!=rb){
            val+=Cost;
            sol[++k].x=b;
            sol[k].y=a;
            if(t[ra]<t[rb]){
                t[ra]+=t[rb];
                t[rb]=ra;
            }
            else{
                t[rb]+=t[ra];
                t[ra]=rb;
            }
        }
    }
    fout<<val<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}