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

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

struct edge
{
	int s, d, c;
};

struct subset
{
	int parent;
	int rank;
};

int find(subset subsets[], int i)
{
	// find root and make root as parent of i (path compression) 
	if (subsets[i].parent != i)
		subsets[i].parent = find(subsets, subsets[i].parent);

	return subsets[i].parent;
}

void Union(subset subsets[], int x, int y)
{
	int xroot = find(subsets, x);
	int yroot = find(subsets, y);

	// Attach smaller rank tree under root of high rank tree 
	// (Union by Rank) 
	if (subsets[xroot].rank < subsets[yroot].rank)
		subsets[xroot].parent = yroot;
	else if (subsets[xroot].rank > subsets[yroot].rank)
		subsets[yroot].parent = xroot;

	// If ranks are same, then make one as root and increment 
	// its rank by one 
	else
	{
		subsets[yroot].parent = xroot;
		subsets[xroot].rank++;
	}
}

bool cmp(const edge& a, const edge& 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<edge>& edges, int n)
{
	int sum = 0;
	sort(edges.begin(), edges.end(), cmp);
	vector<int>parent(n + 1, -1);

	subset *subsets=new subset[n+1];
	for (int i = 1; i <= n; i++)
		subsets[i].parent = i, subsets[i].rank = 0;


	vector<edge>res;
	int i = 0;

	while (res.size() != n - 1)
	{
		edge a = edges[i];
		int u = a.s;
		int v = a.d;

		int x = find(subsets, u);
		int y = find(subsets, v);
		if (x != y)
		{
			res.push_back(a);
			Union(subsets, u, v);
			sum += a.c;
		}

		/*
		int x = find(parent, u);
		int y = find(parent, v);

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

int main()
{

	int n, m;
	f >> n >> m;
	//vector<vector<edge>>graf(n + 1);
	vector<edge>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;
}