#include <cstdio>   
#include <vector>   
#include <algorithm>   

using namespace std;   
  
int n,m,t[200005],costapm,t1,t2;   
  
struct muchie   
{
	int x,y,c;   
};   
vector <muchie> a,g;   
  
int cmp(muchie x,muchie y)   
{   
    return x.c < y.c;   
}   
  
int tata(int x)   
{   
    int y=x,z,aux;   
    while(y!=t[y])   
        y=t[y];   
    z=x;   
    while(z!=t[z])   
    {   
        aux=t[z];   
        t[z]=y;   
        z=aux;   
    }   
    return y;   
}   

  
int main()   
{   
    freopen("apm.in","r",stdin);   
    freopen("apm.out","w",stdout);   
  
    int i;   
    muchie xx;   
  
    scanf("%d %d",&n,&m);
	
    for (i=1;i<=m;++i)   
    {   
        scanf("%d %d %d",&xx.x, &xx.y,&xx.c);   
        g.push_back(xx);   
    }   
	
    for (i=1;i<=n;++i) 
		t[i]=i;   
  
    sort(g.begin(),g.end(),cmp);   
  
    for (i=0;i<m;++i)   
    {   
        t1=tata(g[i].x); 
		t2=tata(g[i].y);   
        if (t1!=t2)   
        {   
            costapm+=g[i].c;   
            t[t1]=t2;   
            a.push_back(g[i]);   
        }   
    }   
  
    printf("%d\n",costapm);
    printf("%d\n", n-1);	
    for (i=0;i<n-1;++i) 
		printf("%d %d\n", a[i].x,a[i].y);   
	
	fclose(stdin);
	fclose(stdout);
	
    return 0;   
}