#include<fstream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<queue>
using namespace std;

void read();
void APM();
void write();

bitset<200001 > s;
vector<vector<int> > a, c;
int n, m;
int cost_total;
queue< pair<int, int> > sol;

int main()
{
	read();
	APM();
	write();
	return 0;
}

void read()
{
	ifstream fin("apm.in");
	
	fin >> n >> m;
	
	a.resize(n+1);
	c.resize(n+1);
	int x, y, z;
	for(int i = 1; i <= m; i++)
	{
		fin >> x >> y >> z;
		a[x].push_back(y);
		a[y].push_back(x);
		c[x].push_back(z);
		c[y].push_back(z);
	}
	
	fin.close();
}

void APM()
{
	//selectez primul nodd
	s[1] = 1;
	int minim = 1500, lin, col;
	for(int i = 0; i < (int)a[1].size(); ++i)
		if( c[1][i] < minim )
		{
			minim = c[1][i];
			lin = 1;
			col = a[1][i];
			cost_total = c[1][i];
		}
		s[col] = 1;
	
		sol.push( make_pair(lin, col) );
		
	// caut muchie usoara si selectez capetele ei
	
	for(int k = 2; k <= n; k++)
	{
		minim = 1500;
		for(int i = 1; i <= n; i++)
			if( s[i] == 1)
			{
				for(int j = 0; j < (int)c[i].size(); ++j)
					if( c[i][j] < minim  && s[ a[i][j] ] != 1)
					{
						minim = c[i][j];
						lin = i;
						col = a[i][j];
					}
			}
		s[col] = 1;
		if(minim != 1500) cost_total += minim;
		sol.push( make_pair(lin, col) );
	}
			
}
					
		
void write()
{
	ofstream fout("apm.out");
	
	fout << cost_total << '\n';
	fout << n - 1 << '\n';
	
	int i = sol.size();
	while ( i >= 2)
	{
		--i;
		fout << sol.front().first << " " << sol.front().second << '\n';
		sol.pop();
	}
	
	fout.close();
}