#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,k,m,viz[200005],a,b,aa[200005],bb[200005],rez,r1,r2;
long long rezz;
struct nod {   
	int x;  
	int y;  
	int cost;
	}v[200005]; 
	
int cmp(const nod a,const nod b)
{     return a.cost<b.cost; } 

int find(int t) 
{   
	while(viz[t]!=0) t=viz[t];  
	return t;
	}   

int main()
{     
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout); 
    scanf("%d %d",&n,&m);   
	for (i=1;i<=m;i++) scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
	sort(v+1,v+m+1,cmp);  
	for (i=1;i<=m;i++) 
		if (find(v[i].x)!=find(v[i].y))  
			{             
				rezz=rezz+v[i].cost;        
				r1=find(v[i].x),r2=find(v[i].y);   
				if (r1>r2) viz[r2]=r1;else viz[r1]=r2;               
				rez++;                
				aa[rez]=v[i].x;          
				bb[rez]=v[i].y;    
				}     
		printf("%lld\n",rezz); 
		printf("%d\n",rez);  
		for (i=1;i<=rez;i++)printf("%d %d\n",bb[i],aa[i]);   
		return 0; 
}