#include <bits/stdc++.h>

using namespace std;

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

const int N = 200000, M = 400000;
int sef[200001];

struct edge
{
	int a, b, c;
}e[400001];

bool cmp(edge e1, edge e2)
{
	return e1.c < e2.c;
}

int Find(int i)
{
	if(sef[i] == i)
		return i;
    sef[i] = Find(sef[i]);
	return sef[i];
}

void Union(int i, int j)
{
	int sefI = Find(i), sefJ = Find(j);
	sef[sefJ] = sefI;
}

int main()
{

	int n, m;
	fin >> n >> m;

	for(int i = 1; i <= m; i++)
		fin >> e[i].a >> e[i].b >> e[i].c;

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

	for(int i = 1; i <= n; i++)
		sef[i] = i;

	int cost = 0;
	vector <edge> ans;
	for(int i = 1; i <= m; i++)
    {
		if(Find(e[i].a) != Find(e[i].b))
		{
			Union(e[i].a, e[i].b);
			ans.push_back(e[i]);
			cost += e[i].c;
		}
		if((int)ans.size() == n - 1)
			i = m;
	}

	fout << cost << '\n' << n - 1 << '\n';

	for(auto j : ans)
		fout << j.a << ' ' << j.b << '\n';

	return 0;
}