#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
struct Muchie{int x,y,cost;};
Muchie G[400010];
int arbore[200010],c[200010];

inline bool Ordonare(const Muchie A,const Muchie B)
{
	if(A.cost==B.cost)
	{
		if(A.x==B.x)
			return A.y<B.y;
		return A.x<B.x;
	}
	return A.cost<B.cost;
}

void Initializari()
{
	int i;
	freopen("apm.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d %d %d",&G[i].x,&G[i].y,&G[i].cost);
	for(i=1;i<=n;i++)
		c[i]=i;
}

void Kruskal()
{
	int i,j,minim,maxim,nr=0; //nr = numarul de muchii selectate
	for(i=1;nr<n-1;i++)
	{
		if(c[G[i].x]!=c[G[i].y]) //daca muchia nu ar forma cicluri cu cele deja selectate
		{
			arbore[++nr]=i; //selectez muchia i
			//unific cele doua componente conexe
			if(c[G[i].x]<c[G[i].y])
			{
				minim=c[G[i].x];
				maxim=c[G[i].y];
			}
			else
			{
				minim=c[G[i].y];
				maxim=c[G[i].x];
			}
			for(j=1;j<=n;j++)
				if(c[j]==maxim)
					c[j]=minim;
		}
	}
}

void AfisareArbore()
{
	freopen("apm.out","w",stdout);
	int i,cost=0;
	for(i=1;i<n;i++)
	{
		cost+=G[arbore[i]].cost;
	}
	printf("%d\n",cost);
	printf("%d\n",n-1);
	for(i=1;i<n;i++)
	{
		printf("%d %d\n",G[arbore[i]].x,G[arbore[i]].y);
	}
}

int main()
{
	Initializari();
	
	sort(G+1,G+m+1,Ordonare); //sortez muchiile crescator dupa cost
	
	Kruskal(); //determin arborele partial de cost minim
	//selectand n-1 muchii de cost minim,care nu formeaza cicluri
	
	AfisareArbore(); //afisez APM
	
	return 0;
}