#include<vector>
#include<fstream>
#include<queue>

using namespace std;

const int cmax = 1001;
ifstream f("apm.in");
ofstream o("apm.out");

class Graph
{
	//vector<vector<int>> adjList;
	vector<vector<pair<int, int>>> adjListW;

public:
	int size;
	Graph(int n)
	{
		size = n;
		//adjList.resize(size);
		adjListW.resize(size);
	}
	/*void addEdgeDirected(int start, int end)
	{
		adjList[start].push_back(end);
	}
	void addEdgeUnirected(int start, int end)
	{
		adjList[start].push_back(end);
		adjList[end].push_back(start);
	}*/
	void addEdgeWeighted(int start, int end, int weight)
	{
		adjListW[start].push_back(make_pair(end, weight));
		adjListW[end].push_back(make_pair(start, weight));
	}
	void MST()
	{
		int Tcost = 0, src = 0;
		priority_queue< pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>> > pq;
		vector<int> parent(size, -1);
		vector<int> cost(size, cmax);                                  
		vector<bool> inMST(size, false);
		pq.push(make_pair(0, src));
		cost[src] = 0;
		while (!pq.empty())
		{
			int u = pq.top().second;
			pq.pop();
			if (!inMST[u])
			{
				inMST[u] = true;
				for (auto i : adjListW[u])
				{
					int v = i.first;
					int weight = i.second;
					if (!inMST[v] && cost[v] > weight)
					{
						cost[v] = weight;
						pq.push(make_pair(cost[v], v));
						parent[v] = u;
					}
				}
			}
		}
		for (auto elem : cost)
			Tcost += elem;
		o << Tcost << endl;
		o << size - 1 << endl;
		for (int i = 1; i < size; i++)
			o << parent[i] + 1 <<" "<< i + 1 << endl;


	}

};


int main()
{

	int N, M;
	int x, y, w;
	f >> N >> M;
	Graph g(N);
	for (int i = 1; i <= M; i++)
	{
		f >> x >> y >> w;
		g.addEdgeWeighted(x - 1, y - 1, w);
	}
	g.MST();

	return 0;
}