#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define N 400001

int n,m,ind[N],g[N],i,x[N],y[N],c[N],a;
vector<int> v;

inline bool cmp (int j,int k){
	return c[j]<c[k];}
	
inline int find (int x){
	return g[x]==x?x:(g[x]=find(g[x]));}
	
inline void unit (int j,int k){
	g[find(j)]=find(k);}

int main ()
{
	
	ifstream in ("apm.in");
	freopen ("apm.out","w",stdout);
	in>>n>>m;
	for(i=1;i<=m;++i){
		in>>x[i]>>y[i]>>c[i];
		ind[i]=i;}
	for(i=1;i<=n;++i)
		g[i]=i;
	sort(ind+1,ind+m+1,cmp);
	for(i=1;i<=m;++i)
		if(find(x[ind[i]])!=find(y[ind[i]])){
			a+=c[ind[i]];
			unit(x[ind[i]],y[ind[i]]);
			v.push_back(ind[i]);}
	printf("%d\n%d\n",a,n-1);
	for(vector<int>::iterator j=v.begin();j<v.end();++j)
		printf("%d %d\n",x[*j],y[*j]);
	
	return 0;}