#include<cstdio>
using namespace std;
#define NMaxVf 50
#define NMaxMuchii NMaxVf*(NMaxVf-1)/2
struct Muchie
{
	int e1,e2,cost;
};
Muchie G[NMaxMuchii];
int A[NMaxVf],c[NMaxVf];
int n,m;
void initializare()
{
	int i;
	freopen("apm.in","r",stdin);
	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]=i;
}
void afisare()
{
	int i, CostAPM=0;
	freopen("apm.out","w",stdout);
	for(i=1;i<n;i++)
		CostAPM+=G[A[i]].cost;
	printf("%d\n%d\n",CostAPM, n-1);
	for(i=1;i<n;i++)
		printf("%d %d\n", G[A[i]].e1, G[A[i]].e2);
}
void sortare(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;
		sortare(st,i-1);
		sortare(i+1,dr);
	}
}
int main()
{
	int i,j,min, max,NrMSel;
	initializare();
	sortare(1,m);
	NrMSel=0;
	for(i=1;NrMSel<n-1;i++)
		if(c[G[i].e1]!=c[G[i].e2])
		{
			A[++NrMSel]=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;
		}
	afisare();
	return 0;
}