// Algoritmul lui Kruskal - O(M log M)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int MAX_N = 2e5, MAX_M = 4e5;
int n, m, t[MAX_N + 1], r[MAX_N + 1];

struct muchie
{
	int x, y;
	short cost;
} v[MAX_M + 1];

inline bool cmp(muchie a, muchie b)
{
	if (a.cost > b.cost)
		return 0;
	return 1;
}

void Citire()
{
	f >> n >> m;

	for (int i = 1; i <= m; i++)
		f >> v[i].x >> v[i].y >> v[i].cost;

	f.close();
}

int Find(int x)
{
	if (t[x] == 0)
		return x;
	return (t[x] = Find(t[x]));
}

void Union(int x, int y)
{
    if (r[x] < r[y])
        t[x] = y;
    else
    {
        t[y] = x;
        if (r[x] == r[y])
            r[x]++;
    }
}

void Kruskal()
{
	sort(v + 1, v + m + 1, cmp);
	vector<pair<int, int>> sol;

	long long costMin = 0;

	for (int i = 1; i <= m; i++)
	{
		int rx = Find(v[i].x);
		int ry = Find(v[i].y);
		if (rx != ry)
		{
			Union(rx, ry);
			costMin += v[i].cost;
			sol.push_back({v[i].x, v[i].y});
		}
	}

	g << costMin << "\n" << sol.size() << "\n";
	for (auto edge : sol)
		g << edge.first << " " << edge.second << "\n";

	g.close();
}

int main()
{
	Citire();
	Kruskal();
	return 0;
}