#include <cstdio>
#include <cstring>

#define file_in "apm.in"
#define file_out "apm.out"

#define Nmax 200010
#define ii inline

struct muchie {int e1,e2,cost;};

muchie g[Nmax];
int n,m; 
int c[Nmax];
int a[Nmax];
int min,max;

ii void citire()
{
	int i,j;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d", &g[i].e1, &g[i].e2, &g[i].cost);
	}
	for (i=1;i<=n;++i)
	{
		c[i]=1;
	}
}

ii void sort(int st, int dr)
{
	int i,j;
	muchie x;
	if (st<dr)
	{
		x=g[st];
		i=st;
		j=dr;
		while(i<j)
		{
			while(i<j && g[j].cost>=x.cost) j--;
			g[i]=g[j];
			while(i<j && g[i].cost<=x.cost) i++;
			g[j]=g[i];
		}
		g[i]=x;
		sort(st,i-1);
		sort(i+1,dr);
	}
}

ii void solve()
{
	int i,j,nr;
	sort(1,m);
	nr=0;
	for (i=1;nr<n-1;++i)
	{
		a[++nr]=i;
		if (c[g[i].e1]<c[g[i].e2])
            min=c[g[i].e1],
			max=c[g[i].e2];
		else
			min=c[g[i].e2],
			max=c[g[i].e1];
		for (j=1;j<=n;++j)
             if (c[j]==max) c[j]=min;
	}
}

ii void afisare()
{
	int i,j,costapm=0;
	for (i=1;i<n;++i)
		 costapm+=g[a[i]].cost;
	printf("%d\n", costapm);
	printf("%d\n", n-1);
	for (i=1;i<n;++i)
		 printf("%d %d\n", g[a[i]].e2,g[a[i]].e1);
}

int main()
{
	
	citire();
    solve();
    afisare();

	fclose(stdin);
	fclose(stdout);
	
	return 0;
}