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

#define INF 0x3f3f3f3f

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
	int v1, v2;
	int cost;
	bool operator < (const muchie& e) const
	{
		return cost < e.cost;
	}
};
muchie g[200001];
muchie arbore[400001];

int n, m;

bool s[100];
int noduriselectate;
int costminim;
int nrmuchii;


void Read();
void Prim(int nod);
void Write();

int main()
{
	Read();
	Prim(1);
	Write();
	
	fin.close();
	fout.close();
	return 0;
}
void Read()
{
	fin >> n >> m;
	
	int x, y, cost;
	for (int i = 1; i <= m; ++i)
	{	
		fin >> x >> y >> cost;
		g[i].v1 = x;
		g[i].v2 = y;
		g[i].cost = cost;
	}
}
void Prim(int nod)
{
	sort(g+1, g+m+1); 
	s[nod] = true;
	++noduriselectate;
	while (noduriselectate < n)
	{
		for (int i = 1; i <= m; ++i)
		{
			if (s[g[i].v1] == true && s[g[i].v2] == false)
			{
				noduriselectate++;
				costminim += g[i].cost;
				s[g[i].v2] = true;
				++nrmuchii;
				arbore[nrmuchii] = g[i];
				break;
			}
			else if (s[g[i].v1] == false && s[g[i].v2] == true)
			{
				noduriselectate++;
				costminim += g[i].cost;
				s[g[i].v1] = true;
				++nrmuchii;
				arbore[nrmuchii] = g[i];
				break;
			}
		}
	}
}
void Write()
{
	fout << costminim << '\n';
	fout << nrmuchii << '\n';
	
	for (int i = 1; i <= nrmuchii; ++i)
		fout << arbore[i].v1 << ' ' << arbore[i].v2 << '\n';
}