#include "iostream"
#include "fstream"
#include "queue"
#include "vector"

using namespace std;

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

struct Graf {
	unsigned from;
	unsigned to;
	int cost;
};

vector < vector <Graf> > lista;
bool *checked;
int nr_nod;

void Read()
{
	int nr_muchii, x, y, cost;
	in >> nr_nod >> nr_muchii;

	checked = (bool*)calloc(nr_nod+1,sizeof(bool));
	for (int i = 0; i < nr_nod+1; i++) checked[i] = false;
		
	lista.resize(nr_nod+1);
	
	Graf pair ;
	
	for (int i = 0; i < nr_muchii; ++ i)
	{
		in >> x >> y >> cost;

		pair.from = x;
		pair.to = y;
		pair.cost = cost;
		lista[x].push_back(pair);

		pair.from = y;
		pair.to = x;
		pair.cost = cost;
		lista[y].push_back(pair);
	}
}

Graf Find_adjacent(int x, bool &ok)
{
	checked[x] = true;
	Graf pair;
	pair.cost = 10000;
	for (int i = 1; i < nr_nod+1; ++ i)
		if (checked[i]) 
		{
			for (unsigned j = 0; j < lista[i].size(); ++ j)
				if ( !checked[ lista[i][j].to ] )
					if ( lista[i][j].cost < pair.cost ) 
					{
						pair.from = i;
						pair.to = lista[i][j].to;
						pair.cost = lista[i][j].cost;
					}
		} else ok = true;	
	return pair;
}

bool If_checked()
{
	for (int i = 1; i < nr_nod+1; ++i)
		if (!checked[i]) return false;
	return true;
}

void Prim(int &cost, int &nr_pair, vector <Graf> &result) 
{
	bool ok = true;
	Graf c = Find_adjacent(1,ok);
	while(ok)
	{
		ok = false;
		cost += c.cost;
		nr_pair ++;
		result.push_back(c);
		c = Find_adjacent(c.to, ok);
	}
}

void Print(int cost, int nr_pair, vector <Graf> result)
{
	out << cost << "\n" << nr_pair << "\n";
	for (unsigned i = 0; i < result.size(); ++i)
		out << result[i].from << " " << result[i].to << "\n";

}

int main(int argc, char const *argv[])
{
	Read();
	int cost = 0;
	int nr_pair = 0;
	vector <Graf> result;

	Prim(cost, nr_pair, result);
	Print(cost, nr_pair, result);	
	return 0;
}