#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int tata[200005],cnt[200005],n,m,k,ans;

struct muc{
	int x,y,cost;
};
muc v[400005],plm[400005];

int findtata(int nod){
    while(nod!=tata[nod]){
        nod=tata[nod];
    }
    return nod;
}
void unire(int nod1,int nod2){
    if(cnt[nod1]==cnt[nod2]){
        cnt[nod1]++;
    }
    if(cnt[nod1]<cnt[nod2])
         tata[findtata(nod1)]=tata[findtata(nod2)];
    else
         tata[findtata(nod2)]=tata[findtata(nod1)];
 
}
bool samegrup(int nod1,int nod2){
    if(findtata(nod1)==findtata(nod2))
       return 1;
    return 0;
}
bool cmp(muc x, muc y) {
	
	if ( x.cost < y.cost)
		return true;
	return false;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
        tata[i]=i;
        cnt[i]=1;
    }
	for(int i=1;i<=m;i++){
		cin>>v[i].x>>v[i].y>>v[i].cost;
	}
	sort(v+1,v+1+m,cmp);
	for(int i=1;i<=m;i++){
		if(samegrup(v[i].x,v[i].y)==false){
			unire(v[i].x,v[i].y);
			plm[++k]=v[i];
			ans+=v[i].cost;
		}
	}
	cout<<ans<<'\n'<<k<<'\n';
	for(int i=1;i<=k;i++){
		cout<<plm[i].x<<" "<<plm[i].y<<'\n';
	}
}