#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <stack>
#include <tuple>
#include <queue>

using namespace std;

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


class Graph
{

public:
	
	void apm();
};
void Graph::apm()
{
	vector<vector<tuple<int, int>>> adj_list;
	vector<tuple<int, int>> empty;
	vector<bool> visited;
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>> > pq;
	vector<tuple<int, int>> answer;
	int N, E;
	fin >> N >> E;

	for (int i = 0; i < N; i++)
	{
		adj_list.push_back(empty);
		visited.push_back(false);
	}

	int edge1, edge2, cost;
	for (int i = 0; i < E; i++)
	{
		fin >> edge1 >> edge2 >> cost;
		edge1--;
		edge2--;
		adj_list[edge1].push_back(make_tuple(edge2, cost));
		adj_list[edge2].push_back(make_tuple(edge1, cost));
	}

	int sum_apm = 0;
	int optimized_nr_edges_answer = N - 1;
	int optimized_nr_edges = N - 1;


	int start_node = 0;

	for (unsigned int i = 0; i < adj_list[start_node].size(); i++)
	{
		pq.push(make_tuple(get<1>(adj_list[start_node][i]), start_node, get<0>(adj_list[start_node][i])));
	}

	visited[start_node] = true;

	while (!pq.empty() && optimized_nr_edges > 0)
	{
		tuple <int, int, int> mn;
		mn = pq.top();
		while (visited[get<2>(mn)])
		{
			pq.pop();
			mn = pq.top();
		}
		sum_apm = sum_apm + get<0>(mn);
		answer.push_back(make_tuple(get<1>(mn), get<2>(mn)));
		pq.pop();
		optimized_nr_edges--;
		start_node = get<2>(mn);

		for (unsigned int i = 0; i < adj_list[start_node].size(); i++)
		{
			if (!visited[get<0>(adj_list[start_node][i])])
			{
				pq.push(make_tuple(get<1>(adj_list[start_node][i]), start_node, get<0>(adj_list[start_node][i])));
			}

		}
		visited[start_node] = true;
	}
	fout << sum_apm << "\n" << optimized_nr_edges_answer << "\n";

	for (unsigned int i = 0; i < answer.size(); i++)
	{
		fout << get<0>(answer[i]) + 1 << " " << get<1>(answer[i]) + 1 << "\n";
	}


}

int main()
{

	Graph graph;
	graph.apm();
	

	return 0;
}