# include <fstream>
# include <algorithm>
# define DIM 400010
# define a first.first
# define b first.second
# define c second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair<pair<int,int>,int> v[DIM],sol[DIM];
int t[DIM],n,m,x,y,cost,i,rx,ry,k,val;
int rad(int x){
    int aux=x;
    while(t[x]>0)
        x=t[x];
    while(t[aux]>0){
        int y=aux;
        aux=t[aux];
        t[y]=x;
    }
    return x;
}
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;i++){
        x=v[i].b;
        y=v[i].c;
        rx=rad(x);
        ry=rad(y);
        if(rx!=ry){
            sol[++k].a=x;
            sol[k].b=y;
            val+=v[i].a;
            if(t[rx]<t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;
            }
            else{
                t[ry]+=t[rx];
                t[rx]=ry;
            }
        }
    }
    fout<<val<<"\n"<<n-1<<"\n";
    for(i=1;i<n;i++)
        fout<<sol[i].a<<" "<<sol[i].b<<"\n";
    return 0;
}