#include<fstream>
#include<algorithm>
#include<vector>
#include<stdio.h>

using namespace std;

const int maxn = 400100;

int GR[maxn],X[maxn],Y[maxn],COST[maxn];
int n, m,INDICE[maxn];
vector<int> APM;

int Padure(int i)
{
	if (GR[i] == i) return i;
	GR[i] = Padure(GR[i]);
	
	return GR[i];
}

void reuniune(int i,int j)
{
	GR[Padure(i)] = Padure(j);
}

bool cmp(int i,int j)
{
	return(COST[i] < COST[j]);	
}

int main()
{
    int i;
	ifstream f("plan.in");
	
	   f>>n>>m;
	   
	for(i = 1; i<=m;i++)
	{
		f>>X[i]>>Y[i]>>COST[i];
		INDICE[i] = i;
	}
	
	f.close();

	for(int i = 1;i<=n;i++) 
        GR[i] = i;
	
	
	sort(INDICE + 1,INDICE + m + 1,cmp);
	
	
	for(i = 1; i<=m; i++)
	{
		if (Padure(X[INDICE[i]]) != Padure(Y[INDICE[i]]))
		    {
		        	REZ += COST[INDICE[i]];
			        reuniune(X[INDICE[i]],Y[INDICE[i]]); 
			        APM.push_back(INDICE[i]);            
		}
	}
	ofstream g("plan.out");
	g<<REZ<<"\n";
	g<<n - 1<<"\n";
	for(int i = 0;i < n - 1; i++)
		g<<X[APM[i]]<<" "<<Y[APM[i]]<<"\n";
	g.close();
	return 0;
}