#include <fstream>
#include<algorithm>
#define st second.first
#define dr second.second
#define cost first
#define dim 500001
using namespace std;
ifstream fin("APM.in");
ofstream fout("APM.out");
pair < int, pair <int,int> > l[dim];
int n,m,i,t[1001],rx,ry,p[1001],u[1001],k,s;
int rad(int x){
    while(t[x]>0)
        x=t[x];
    return x;

}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++){
    fin>>l[i].st>>l[i].dr>>l[i].cost;
}
sort(l+1,l+m+1);
for(i=1;i<=n;i++)
    t[i]=-1;
for(i=1;i<=m;i++){
    rx=rad(l[i].st);
    ry=rad(l[i].dr);
    if(rx!=ry){
        s+=l[i].cost;
        p[++k]=l[i].st;
        u[k]=l[i].dr;
        if(t[rx]<t[ry]){
            t[rx]+=t[ry];
            t[ry]=rx;
        }else{
            t[ry]+=t[rx];
            t[rx]=ry;
        }
    }
}
fout<<s<<'\n';
fout<<k<<'\n';
for(i=1;i<=k;i++)
    fout<<u[i]<<" "<<p[i]<<'\n';
    return 0;
}