#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="apm.in";
const char OutFile[]="apm.out";
const int MaxN=200111;
const int INF=1<<30;
ifstream fin(InFile);
ofstream fout(OutFile);

struct s_vedge
{
	s_vedge(int to2,int cost2):to(to2),cost(cost2){}
	int to,cost;
};

int N,M,x,y,cost,sum,T[MaxN],D[MaxN],H[MaxN],V[MaxN];
vector<s_vedge> a[MaxN];

inline void init()
{
	H[0]=N;
	H[1]=1; D[1]=0;
	for(register int i=2;i<=N;++i)
	{
		H[i]=i; D[i]=INF;
	}
}

inline int left(int nod)
{
	return nod<<1;
}

inline int right(int nod)
{
	return (nod<<1)+1;
}

inline int father(int nod)
{
	return nod>>1;
}

inline void upheap(int x)
{
	if(x<=H[0])
	{
		int t=father(x);
		while(t!=0 && D[H[t]]>D[H[x]])
		{
			swap(H[t],H[x]);
			x=t;
			t=father(x);
		}
	}
}

inline void downheap(int x)
{
	int a=x,r=right(x),l=left(x);
	if(l<=H[0]) 
	{
		if(D[H[l]]<D[H[a]])
		{
			a=l;
		}
	}
	if(r<=H[0])
	{
		if(D[H[r]]<D[H[a]])
		{
			a=r;
		}
	}
	while(a!=x)
	{
		swap(H[x],H[a]);
		x=a;
		r=right(x);
		l=left(x);
		if(l<=H[0])
		{
			if(D[H[l]]<D[H[a]])
			{
				a=l;
			}
		}
		if(r<=H[0])
		{
			if(D[H[r]]<D[H[a]])
			{
				a=r;
			}
		}
	}
}

inline void delheap(int x)
{
	swap(H[H[0]],H[x]);
	--H[0];
	downheap(x);
}

int main()
{
	fin>>N>>M;
	for(register int i=0;i<M;++i)
	{
		fin>>x>>y>>cost;
		a[x].push_back(s_vedge(y,cost));
		a[y].push_back(s_vedge(x,cost));
	}
	fin.close();

	init();
	for(register int i=1;i<=N;++i)
	{
		sum+=D[H[1]];
		int nod=H[1];
		V[nod]=1;
		delheap(1);
		for(vector<s_vedge>::iterator it=a[nod].begin();it!=a[nod].end();++it)
		{
			if(V[it->to]==0)
			{
				if(D[it->to]>it->cost)
				{
					D[it->to]=it->cost;
					T[it->to]=nod;
				}
			}
		}
		for(register int i=H[0];i>0;--i)
		{
			upheap(i);
		}
	}

	fout<<sum<<"\n"<<N-1<<"\n";
	for(register int i=2;i<=N;++i)
	{
		fout<<i<<" "<<T[i]<<"\n";
	}
	fout.close();
	return 0;
}