// Alg. lui Prim

#include <fstream>
using namespace std;

ofstream fout("amp.out");

const int DIM = 100;
const int INFINIT = 10000;

int a[DIM][DIM];


int m, n;
int costmin;    
int tata[DIM];  
int s[DIM];     
int nr=0;

void Read();
void Prim(int);


int main()
{
	Read();
	Prim(1);

	fout.close();
	return 0;
}

void Read()
{
	ifstream fin("amp.in");
	int v1, v2, cost;
	fin >> n >> m;

	for ( int i = 1; i <= m; i++ )
	{
		fin >> v1 >> v2 >> cost;
		a[v1][v2] = a[v2][v1] = cost;
	}
	fin.close();
}


void Prim(int nod)
{
	int tv, v;
	int u = 1;   
	int q[100];  
	q[1] = nod;
	s[nod] = 1;

	while ( u < n ) 
	{
		int min = INFINIT;
		for ( int i = 1; i <= u; i++ )  // i poz in sirul q
		{
			for ( int j = 1; j <= n; j++ )
				if ( a[q[i]][j] < min && !s[j] && a[q[i]][j] ) 
				{
					min = a[q[i]][j];
					v = j;      
					tv = q[i];  
				}
		}
		costmin += min; 
        nr++; 
         
		fout << tv << " " << v << endl;
		s[v] = 1;
		tata[v] = tv;
		q[++u] = v;
	}
	 	fout<<costmin<<endl;
		fout<<nr << endl;
	
}