#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

#define pb push_back

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

const int maxn = 400100;
	
int GR[maxn],X[maxn],Y[maxn],C[maxn];
int N,M,ANS,IND[maxn];
vector<int> VANS;
	 
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 Sortare(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,Sortare);
	
	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';
	fout << N - 1 << '\n';
	
	for(int i = 0;i < N - 1; ++i)
		fout << X[VANS[i]] << ' ' << Y[VANS[i]] << '\n';
	
	fin.close();
	fout.close();
	
	return 0;
}