//Kruskal
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;

const int maxn = 400100;

int gr[maxn], x[maxn], y[maxn], c[maxn], n, m, ans, ind[maxn];
vector <int> vans;

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

int grupa(int i)
{
	if(gr[i] == i)
		return i;
	gr[i] = grupa(gr[i]);
	return gr[i];
}

void reuniune(int i, int j)
{
	gr[grupa(i)] = grupa(j);
}

bool cmpf(int i, int j)
{
	return (c[i] < c[j]);
}

int main()
{
	fin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		fin>>x[i]>>y[i]>>c[i];
		ind[i] = i;
	}
	for(int i=1;i<=n;++i)
		gr[i] = i;
	for(int i=1;i<=n;++i)
		gr[i] = i;
	sort(ind+1, ind+m+1, cmpf);
	for(int i=1;i<=m;++i)
	{
		if(grupa(x[ind[i]]) != grupa(y[ind[i]]))
		{
			ans += c[ind[i]];
			reuniune(x[ind[i]],y[ind[i]]);
			vans.pb(ind[i]);
		}
	}
	fout<<ans<<'\n'<<n-1<<'\n';
	for(int i=0; i<n-1; ++i)
	fout<<x[vans[i]]<<' '<<y[vans[i]]<<'\n';
	return 0;
	
}