#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m,viz[10000],tata[10000];
vector <pair <int,int> > v[10000];
int main()
{
	ifstream f ("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	int i,j,k,l,d,s,mini=1000000,cost=0;
	for(i=1;i<=m;i++)
	{
		f>>j>>k>>l;
		v[j].push_back(make_pair(k,l));
		v[k].push_back(make_pair(j,l));
	}
	viz[1]=1;
	tata[1]=0;
	for(k=1;k<n;k++)
	{
		mini=1000000;
		for(i=1;i<=n;i++)
			for(j=0;j<v[i].size();j++)
			{
				l=v[i][j].first;
				if((viz[i]==1)&&(viz[l]==0)&&(mini>v[i][j].second))
				{
					mini=v[i][j].second;
					s=i;
					d=l;
				}
			}
		viz[d]=1;
		tata[d]=s;
		cost=cost+mini;
	}
	g<<cost<<endl<<n-1<<endl;
	for(i=2;i<=n;i++)
		if((tata[i]!=0)&&(i!=1))
			g<<i<<" "<<tata[i]<<endl;
}