#include <fstream>
using namespace std;

#define nmax 200001
int n, m;
bool viz[nmax];
long s, C;

struct muchii
{
	int x, y, c;
	bool used;
}M[2*nmax];

void citire()
{
	ifstream in("apm.in");
	in>>n>>m;
	for(int i=1; i<=m; i++)
		in>>M[i].x>>M[i].y>>M[i].c;
}

void afisare()
{
	ofstream out("apm.out");
	out<<s<<"\n"<<C<<"\n";
	for(int i=1; i<=m; i++)
		if(M[i].used)
			out<<M[i].x<<" "<<M[i].y<<"\n";
	
}

void apm()
{
	int i, cost, poz;
	viz[1] = 1;
	for(int j=1; j<n; j++)
	{
		cost = 1001; poz = 0;
		for(i=1; i<=m; i++)
			if( (viz[M[i].x] && !viz[M[i].y]) || (viz[M[i].y] && !viz[M[i].x]) && M[i].c < cost)
				poz = i, cost = M[i].c;
		viz[M[poz].x] = viz[M[poz].y] = M[poz].used = 1;
	}
}

void solve()
{
	for(int i=1; i<=m; i++)
		if(M[i].used)
			C++, s += M[i].c;
}

int main()
{
	citire();
	apm();
	solve();
	afisare();
	return 0;
}