#include <bits/stdc++.h>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
bool parc[200100];
std::vector<std::pair<int, std::pair<int, int> > > v[200100], muchii, sol;
int solp = 0;
int n, m;

bool totparc() {
	for (int i = 1; i <= n; ++i)
	{
		if (!parc[i]) {return 0;}
	}
	return 1;
}

int main()
{
	fin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b, cost;
		fin >> a >> b >> cost;
		v[a].push_back(std::make_pair(cost, std::make_pair(b, a)));
		v[b].push_back(std::make_pair(cost, std::make_pair(b, a)));
	}
	int front = 1;
	while (!totparc()) {
		parc[front] = 1;
		for (std::vector<std::pair<int, std::pair<int, int> > >::iterator i = v[front].begin(); i != v[front].end(); ++i)
		{
			muchii.push_back(*i);
		}
		std::sort(muchii.begin(), muchii.end());
		for (std::vector<std::pair<int, std::pair<int, int> > >::iterator i = muchii.begin(); i != muchii.end(); ++i)
		{
			if (!parc[i->second.first]) {
				front = i->second.first;
				sol.push_back(*i);
				solp+=i->first;
				break;
			}
		}
	}
	fout<<solp<<"\n";
	fout<<sol.size()<<"\n";
	for (std::vector<std::pair<int, std::pair<int, int> > >::iterator i = sol.begin(); i != sol.end(); ++i)
	{
		fout << i->second.first << " " << i->second.second <<" "<<i->first << "\n";
	}
}