//#include "pch.h"
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct edg
{
	int first, second, cost;
};

class cmp
{
public:
	const bool operator () (const edg a, const edg b)
	{
		return a.cost < b.cost;
	}
};

int n, m, sum;
int father[200005];
edg edge[400005];
vector <int> ans;

int parent(int a)
{
	if (father[a] == a)
		return a;
	
	father[a] = parent(father[a]);
	return father[a];
}

void unite(int a, int b)
{
	father[parent(a)] = parent(b);
}

int main()
{
	ios::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) fin >> edge[i].first >> edge[i].second >> edge[i].cost;
	
	for (int i = 1; i <= n; ++i) father[i] = i;

	sort(edge + 1, edge + m + 1, cmp());

	for (int i = 1; i <= m; ++i)
	{
		if (parent(edge[i].first) == parent(edge[i].second)) continue;

		unite(edge[i].first, edge[i].second);
		sum += edge[i].cost;
		ans.push_back(i);
	}

	fout << sum << '\n';
	fout << ans.size() << '\n';
	
	for (auto x : ans) fout << edge[x].first << " " << edge[x].second << '\n';
}