#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

class Graf
{
	int n, m;
	vector <vector<pair<int,int>>> adiacenta;

	int drumMin(vector <bool> viz, vector <int> cost);

public :
	Graf(int n, int m, vector <vector<pair<int, int>>> adiacenta);

	void algPrim();
};

Graf::Graf(int n, int m, vector <vector<pair<int, int>>> adiacenta)
{
	this->n = n;
	this->m = m;
	this->adiacenta = adiacenta;
}


int Graf::drumMin(vector <bool> viz, vector <int> cost) // select drum min
{
	int nod,costMin = 1001;
	for (int i = 1; i <= n; ++i)
	{
		if (viz[i] == false && cost[i] < costMin)
		{
			costMin = cost[i];
			nod = i;
		}
	}
	return nod ;
}

void Graf::algPrim()
{
	vector <bool> viz(n + 1, false);
	vector <int> cost(n + 1, 1001);
	vector <int> par(n + 1, -2);
	cost[1] = 0;
	par[1] = -1;
	int nodp;

	for (int i = 1; i <= n; ++i)
	{
		nodp = drumMin(viz, cost);
		viz[nodp] = true;
		//cout << nodp << " " << cost[nodp] << "\n";
		for (auto nodc : adiacenta[nodp])
		{
			if (viz[nodc . first] == false && cost[nodc.first] > nodc.second)
			{
				par[nodc.first] = nodp;
				cost[nodc.first] = nodc.second;
			}
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		//cout << cost[i] << " ";
		sum += cost[i];
	}
	out << sum << "\n" << n - 1 << "\n";
	for (int i = 2; i <= n; ++i)
		out << i << " " << par[i] << "\n";

}

void p1()
{
	int n, m, x, y, z;
	in >> n >> m;
	vector <vector<pair<int, int>>> adiacenta(n + 1);

	for (int i = 1; i <= m; ++i)
	{
		in >> x >> y >> z;
		adiacenta[x].push_back(make_pair(y, z));
		adiacenta[y].push_back(make_pair(x, z));
	}
	Graf g(n, m, adiacenta);
	g.algPrim();
}

int main()
{
	p1();
}