#include<fstream>
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;
	ifstream fin("apm.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
		fin>>G[i].x>>G[i].y>>G[i].cost;
	fin.close();
	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()
{
	ofstream fout("apm.out");
	int i,cost=0;
	for(i=1;i<n;i++)
	{
		cost+=G[arbore[i]].cost;
	}
	fout<<cost<<"\n"<<n-1<<"\n";
	for(i=1;i<n;i++)
	{
		fout<<G[arbore[i]].x<<' '<<G[arbore[i]].y<<"\n";
	}
	fout.close();
}

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;
}