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

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

struct edge
{
	int n, cost;
};
struct edge2
{
	int s, d, c;
};

int myComp(const edge2& a, const edge2& b)
{
	return a.c < b.c;
}


int find(vector<int>&parent, int i)
{
	if (parent[i] == -1)
		return i;
	return find(parent, parent[i]);
}

void Union(vector<int>& parent, int x, int y)
{
	int xset = find(parent, x);
	int yset = find(parent, y);
	if (xset != yset) {
		parent[xset] = yset;
	}
}

void Kruskal(vector<edge2>& edges,int n)
{
	int sum = 0;

	vector<edge2>res;
	int i = 0;

	vector<int>parent(n + 1, -1);

	sort(edges.begin(), edges.end(), myComp);
	while (res.size() != n - 1)
	{
		edge2 next_edge = edges[i++];
		int x = find(parent, next_edge.s);
		int y = find(parent, next_edge.d);

		if (x != y)
		{
			res.push_back(next_edge);
			sum += next_edge.c;
			Union(parent, x, y);
		}
	}
	g << sum << "\n";
	g << res.size() << "\n";
	for (int i = 0; i < res.size(); i++)
		g << res[i].s << " " << res[i].d << "\n"; //<< res[i].c << "\n";
}

int main()
{

	int n, m;
	f >> n >> m;
	vector<vector<edge>>graf(n + 1);
	vector<edge2>edges;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		f >> x >> y >> z;
		graf[x].push_back({ y,z });
		graf[y].push_back({ x,z });
		edges.push_back({ x,y,z });
	}
	//cout<<is_cycle(n, edges);
	Kruskal(edges, n);
	return 0;
}