#include<fstream>
#define nmaxvf 50
#define nmaxmuchii nmaxvf*(nmaxvf-1)/2
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

 struct muchie
 {
	 int e1,e2,cost;
	 
 };
 muchie G[nmaxmuchii];
 int a[nmaxvf],c[nmaxvf],n,m;
 void initializare()
 {
	 int i;
	 f>>n>>m;
	 for(i=1;i<=m;i++)
		 f>>G[i].e1>>G[i].e2>>G[i].cost;
	 for(i=1;i<=n;i++)
		 c[i]=i;
 }
    void afisare()
	{
		int i,costapm=0,nr=0;
		for(i=1;i<n;i++)
		{
			costapm+=G[a[i]].cost;
			nr++;
		}
		g<<costapm<<"\n";
		g<<nr<<"\n";
		for(i=1;i<n;i++)
		{
			g<<G[a[i]].e2<<" "<<G[a[i]].e1<<"\n";
		}
		}
	void sortmuchii(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;
			sortmuchii(st,i-1);
			sortmuchii(i+1,dr);
		}
}

int main()
{
		int i,j,min1,max1,nrmsel;
		initializare();
		sortmuchii(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])
				{
					min1=c[G[i].e1];
					max1=c[G[i].e2];
				}
				else
				{
					min1=c[G[i].e2];
					max1=c[G[i].e1];
				}
				for(j=1;j<=n;j++)
					if(c[j]==max1)
						c[i]=min1;
			}
			afisare();
			return 0;
	}