#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define pb push_back

using namespace std;


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

const int maxn = 400100;

int G[maxn],X[maxn],Y[maxn],C[maxn];
int n,m,ans,IND[maxn];
vector<int>v;

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

void reuniune(int i,int j)
{
	G[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) G[i] = i;
	for(int i = 1;i <= n; ++i) G[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]]);
			v.pb(IND[i]);
		}
	}
	fout<<ans<<endl;
	fout<<n-1<<endl;
	for(int i = 0;i < n - 1; ++i)
	 fout<<X[v[i]]<<" "<<Y[v[i]]<<endl;
	return 0;
}