#include<fstream>
#include<algorithm>

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
 
 struct Lat{ 
 	int x, y, cost;
 }A[400005];
 
 struct Arb{
 	int x, y;
 }T[400005];
 
int u[200005], i, j, k, n, m, a, b, S;

bool cmp(const Lat &x,const Lat &y){
	return x.cost<y.cost;
}


int SK(int x){
	if (x==u[x]) return x;
	else {
		u[x]=SK(u[x]); 
		return u[x];
	}
}

int main()
{
 	
 	cin>>n>>m;
 	for (i=1; i<=n; ++i) u[i]=i;
 	
 	for(i=1; i<=m; ++i) cin>>A[i].x>>A[i].y>>A[i].cost;
 	
 	sort(A+1, A+m+1, cmp);
 	for(i=1; i<=m; ++i){ 		
 		a=SK(A[i].x);
 		b=SK(A[i].y);
 		if (a!=b){
 			S+=A[i].cost;
 			u[b]=a;
 			T[++k].x=A[i].x;
 			T[k].y=A[i].y;
		 }
		 
	 }
 		
 	cout<<S<<'\n';
 	cout<<k<<'\n';
 	for(i=1; i<=k; ++i) cout<<T[i].x<<' '<<T[i].y<<'\n';
 	
 
 return 0; 
}