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

inline bool Ordonare(Muchie A,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;
	Muchie aux;
	freopen("apm.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&aux.x,&aux.y,&aux.cost);
		H.push_back(aux);
	}
}

int Find(int x)
{
	int r=x;
	while(c[r])
		r=c[r];
	int y=x,aux;
	while(y!=r)
	{
		aux=c[y];
		c[y]=r;
		y=aux;
	}
	return r;
}

void Union(int x,int y)
{
	if(h[x]>h[y])
		c[y]=x;
	else
	{
		c[x]=y;
		if(h[x]==h[y])
			h[y]++;
	}
}

void Kruskal()
{
	int i,A,B,nr=0; //nr = numarul de muchii selectate
	Muchie aux;
	for(i=1;nr<n-1;i++)
	{
		aux=H.front(); //selectez din min-heap muchia de cost minim
		pop_heap(H.begin(),H.end(),Ordonare);
		H.pop_back();
		
		A=Find(aux.x);
		B=Find(aux.y);
		
		if(A!=B) //daca muchia nu ar forma cicluri cu cele deja selectate
		{
			arbore[++nr]=aux; //selectez muchia aux
			Union(A,B); //unific cele doua componente conexe
		}
	}
}

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

int main()
{
	Initializari();
	
	make_heap(H.begin(),H.end(),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;
}