#include<fstream>
#include<algorithm>
using namespace std;

#define NMAX 10000

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

int car[NMAX];
int n, m;
pair<int , pair<int , int> > a[NMAX], arb[NMAX];
int cost_arb;

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

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

void APM()
{
	sort(a, a + m);  
	
	for(int i = 1; i <= n; i++)
		car[i] = i;
	
	int k = 0;
	
	for(int i = 0; i < m; i++)
	{
		int c1 = car[ a[i].second.first ];
		int c2 = car[ a[i].second.second];
		
		if(c1 != c2)
		{
			arb[k++] = a[i];
			cost_arb += a[i].first;
			
			for(int j = 1; j <=	n; j++)
				if( car[j] == c2)
					car[j] = c1;
				
			if(k == n-1) break;
		}
	}
	
}

void write()
{
	ofstream fout("apm.out");
    fout << cost_arb << '\n';
	fout << n - 1 << '\n';
	for(int i = 0; i < n-1; i++)
		fout << a[i].second.second <<" "<<a[i].second.first << '\n';
}