//kruskal
#include <iostream>
#include <vector>
#include <fstream>
#include <tuple>
#include <algorithm>

using namespace std;

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

typedef tuple<int, int, int> tp3;
vector<tp3>vtup;

struct subset
{
	int parent;
	int rank;
}subsets[200005];

int find(const subset subsets[], int i)
{
	if (i != subsets[i].parent)
		return 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);

	if (subsets[xroot].rank > subsets[yroot].rank)
		subsets[yroot].parent = xroot;
	else
		if (subsets[xroot].rank < subsets[yroot].rank)
			subsets[xroot].parent = yroot;
		else
		{
			subsets[yroot].parent = xroot;
			subsets[xroot].rank++;
		}
}


void kruskal(vector<tp3> &vtup, int n)
{
	vector<tp3>rez;
	for (int i = 1; i <= n; i++)
	{
		subsets[i].parent = i;
		subsets[i].rank = 0;
	}

	sort(vtup.begin(), vtup.end(), [](const tp3 &lhs, const tp3 &rhs) {return get<2>(lhs) < get<2>(rhs); });
	for (auto &t : vtup)
	{
		auto[a, b, w] = t;
		int roota = find(subsets, a);
		int rootb = find(subsets, b);
		if (roota==0 || rootb==0 || roota!=rootb)
		{
			rez.push_back(t);
			Union(subsets, a, b);
		}
	}
	int cost = 0;
	for (auto &it : rez)
	{
		cost += get<2>(it);
	}
	fout << cost << '\n' << rez.size() << '\n';
	for (auto &it : rez)
		fout << get<0>(it) << ' ' << get<1>(it) << '\n';


}

int main()
{
	int n, m;
	fin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		fin >> a >> b >> w;
		vtup.push_back({ a,b,w });
	}
	kruskal(vtup, n);
}