#include <fstream>

using namespace std;
ifstream f("date.in");
ofstream g("date.out");
int n,m,i,j,ct,k,t[10001],nrm,rang[1001];
struct muchii{
    int x; int y; int cost;
}b[10001],aux,sol[10001];

int main()
{f>>n>>m;
for(i=1;i<=m;i++)f>>b[i].x>>b[i].y>>b[i].cost;

for(i=1;i<=m;i++)for(j=i+1;j<=m;j++){
    if(b[i].cost>b[j].cost){
        aux=b[i];
        b[i]=b[j];
        b[j]=aux;
    }
}
ct=0;
k=0;

for(i=1;i<=n;i++){t[i]=i; rang[i]=1;}
i=1;
while(k<n-1){
    if(t[b[i].x]!=t[b[i].y]){
        k++;
        ct=ct+b[i].cost;
        nrm++;
        sol[nrm]=b[i];
        if(rang[b[i].y]>rang[b[i].x])
        for(j=1;j<=n;j++){
            if(t[j]==t[b[i].x])
                {t[j]=t[b[i].y]; rang[j]=rang[b[i].y];}
        }
        else if(rang[b[i].y]<rang[b[i].x]){
            for(j=1;j<=n;j++){
            if(t[j]==t[b[i].y])
                {t[j]=t[b[i].x]; rang[j]=rang[b[i].x];}
        }
        }else if(rang[b[i].y]==rang[b[i].x]){
            rang[b[i].y]++;
             for(j=1;j<=n;j++){
            if(t[j]==t[b[i].x])
                {t[j]=t[b[i].y]; rang[j]=rang[b[i].y];}
                rang[b[i].y]++;
        }
        }


    }
    i++;
}

g<<ct<<endl<<nrm<<endl;
for(i=1;i<=nrm;i++)g<<sol[i].y<<" "<<sol[i].x<<endl;

    return 0;
}