# include <fstream>
using namespace std;
struct nod{
	int i, j, c;};
int n, nm, t[200003], cmin, v[400003], rang[200003];
nod m[400003];

void qsort (int st, int dr)
{
	if (st<dr)
	{
		int i=st, j=dr, d=0, q=(st+dr)/2;
		nod a;
		a=m[i], m[i]=m[q], m[q]=a;
		while (i<j)
		{
			if (m[i].c>m[j].c)
			{
				a=m[i], m[i]=m[j], m[j]=a;
				d=1-d;
			}
			i+=d;
			j-=1-d;
		}
		qsort (st, i-1);
		qsort (i+1, dr);
	}
}

int rad (int k)
{
	int y=k, i;
	while (t[k]) k=t[k];
	while (y!=k)
	{
		i=t[y];
		t[y]=k;
		y=i;
	}
	return k;
}

int main ()
{
	int ri, rj;
	ifstream fin ("apm.in");
	ofstream fout ("apm.out");
	fin>>n>>nm;
	for (int i=1;i<=nm;i++)
		fin>>m[i].i>>m[i].j>>m[i].c;
	qsort (1, nm);
	for (int i=1;i<=nm;i++)
		if ((ri=rad(m[i].i))!=(rj=rad(m[i].j)))
		{
			if (rang[ri]<rang[rj])
				t[ri]=rj;
			else
				if(rang[ri]>rang[rj])
					t[rj]=ri;
				else
				{				
					t[ri]=rj;
					rang[rj]++;
				}				
				cmin+=m[i].c;
				v[i]=1;
			
			
		}
	fout<<cmin<<endl<<n-1<<endl;
	for (int i=1;i<=nm;i++)
		if (v[i])
			fout<<m[i].i<<" "<<m[i].j<<endl;
	return 0;
}