#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
typedef vector < vector<pair<int, int>>> Graph;


class DisjointSet
{
	vector<int> p;
	vector<int> rang;
public:
	DisjointSet(int n) : p(n, 0), rang(n, 0)
	{
		for (int i = 0; i < n; i++)
			p[i] = i;
	}
	int Find(int x)
	{
		if (p[x] != x)
			p[x] = Find(p[x]);
		return p[x];
	}
	void Union(int x, int y)
	{
		int px = Find(x);
		int py = Find(y);
		if (rang[px] > rang[py])
		{
			p[py] = px;
		}
		else if (rang[px] < rang[py])
		{
			p[px] = py;
		}
		else
		{
			p[py] = px;
			rang[px]++;
		}
	}
};

void Kruskal(Graph& G)
{
	vector<pair<int, pair<int, int>>> edges;
	vector<pair<int, int>> picked_edges;
	for (int i = 0; i < G.size(); i++)
	{
		for (auto it = G[i].begin(); it != G[i].end(); it++)
		{
			edges.push_back({ it->second, { i, it->first } });
		}
	}
	DisjointSet dset(G.size());
	sort(edges.begin(), edges.end());
	int sum = 0;
	for (auto ed = edges.begin(); ed != edges.end(); ed++)
	{
		if (dset.Find(ed->second.first) != dset.Find(ed->second.second))
		{
			dset.Union(ed->second.first, ed->second.second);
			picked_edges.push_back({ ed->second.first, ed->second.second });
			sum += ed->first;
		}
	}
	out << sum << '\n';
	out << picked_edges.size() << '\n';
	for (auto it = picked_edges.begin(); it != picked_edges.end(); it++)
	{
		out << it->first + 1 << ' ' << it->second + 1<< '\n';
	}
}
int main()
{
	int N, M;
	in >> N >> M;
	Graph G(N, vector < pair<int, int>>());

	for (int i = 0; i < M; i++)
	{
		int u, v, c;
		in >> u >> v >> c;
		u--; v--;
		G[u].push_back({ v, c });
	}
	Kruskal(G);
}