// Kruskal de 100 puncte
#include<fstream>
#include<algorithm>
#include<vector>
#define Nmax 200001
#define Mmax 400001
#define pb push_back
using namespace std;
ifstream f("apm.in"); ofstream g("apm.out");
int GR[Nmax],X[Mmax],Y[Mmax],C[Mmax],IND[Mmax];
int N,M,ANS;
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 cmpf(int i,int j) {return(C[i] < C[j]);}
int main()
{	f>>N>>M; 
	for(int i = 1;i <= M;++i) {f>>X[i]>>Y[i]>>C[i]; IND[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]);
			}
	g<<ANS<<'\n'<<N-1<<'\n'; 
	for(int i = 0;i < N - 1; ++i) g<<X[VANS[i]]<<' '<<Y[VANS[i]]<<'\n'; 
	g.close(); return 0;
}