#include <fstream>
#include <set>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m,cost,x,y,c,uz[200005];
vector < pair<int, int> > L[200005],sol;
set < pair< int, pair<int, int> > > S;
int main()
{
	int i, j;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		L[x].pb(mp(y, c));
		L[y].pb(mp(x, c));
	}
	uz[1] = 1;
	for (i = 0; i < L[1].size(); i++)
		S.insert(mp(L[1][i].second, mp(1, L[1][i].first)));
	for (j = 2; j <= n; j++)
	{
		while (uz[(*S.begin()).second.second])
			S.erase(S.begin());
		auto aux = (*S.begin());
		uz[aux.second.second] = 1;
		cost += aux.first;
		for (i = 0; i < L[aux.second.second].size(); i++)
			S.insert(mp(L[aux.second.second][i].second, mp(aux.second.second, L[aux.second.second][i].first)));
		sol.pb(mp(aux.second.first, aux.second.second));
	}
	fout << cost << '\n';
	fout << sol.size() << '\n';
	for (i = 0; i < sol.size(); i++)
		fout << sol[i].first << ' ' << sol[i].second << '\n';
}