#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

typedef struct node {
	int first_verted;
	int second_vertex;
	int value;
}node;

typedef struct compareEdges {
	bool operator()(node const& p1, node const& p2) {
		return p1.value > p2.value;
	}
};
void display_node(node x);


void read(int &vertices_number,int &edges_number,vector<node> &a)
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &vertices_number, &edges_number);

	a.resize(edges_number);

	node new_node;

	for (int i = 0; i < edges_number; i++)
	{
		scanf("%d %d %d", &new_node.first_verted, &new_node.second_vertex, &new_node.value);
		a[i] = new_node;
	}

}


void display(vector<node> &a,int sum)
{
	printf("%d\n%d\n",sum,a.size());
	for (int i = 0; i < a.size(); i++)
	{
		display_node(a[i]);
	}
}

bool compare(node x, node y)
{
	return 1;
}
bool hasSameParent(vector<int> &parent, int first, int second)
{
	int first_aux, second_aux;
	first_aux = first;
	second_aux = second;

	while (parent[first_aux] != first_aux)
	{
		first_aux = parent[first_aux];
	}

	while (parent[second_aux] != second_aux)
	{
		second_aux = parent[second_aux];
	}

	if (first_aux != second_aux)
	{
		parent[second_aux] = parent[first_aux];
		parent[first] = parent[first_aux];
		parent[second] = parent[first_aux];
		return 0;
	}
	return 1;
}
void solve(int vertex_number, vector<node> graph)
{
	priority_queue<node, vector<node>, compareEdges>p_queue;

	make_heap(graph.begin(), graph.end(), compareEdges());

	for (int i = 0; i < graph.size(); i++)
		p_queue.push(graph[i]);

	vector<int>parent(vertex_number + 1, 0);
	for (int i = 1; i <= vertex_number; i++)
	{
		parent[i] = i;
	}
	vector<node> solution;
	int sum = 0;
	
	while (!graph.empty())
	{
		node currentNode = graph.front(); 
		pop_heap(graph.begin(), graph.end(), compareEdges());
		graph.pop_back();
		if (!hasSameParent(parent, currentNode.first_verted, currentNode.second_vertex))
		{
			solution.push_back(currentNode);
			sum += currentNode.value;
		}
	}

	display(solution, sum);
}


void display_node(node x)
{
	printf("%d %d\n", x.first_verted, x.second_vertex);
}

int main()
{
	int vertices_number, edges_number;
	vector<node>graph;

	read(vertices_number, edges_number, graph);

	solve(vertices_number, graph);





	return 0;
}