#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz size
#define N 200010
int n,m,nh,h[N],d[N],inheap[N],t[N],r;
vector< pair<int,int> > a[N],rez;
inline int father(int x)
{
	return x>>1;
}
inline int left_son(int x)
{
	return x<<1;
}
inline int right_son(int x)
{
	return (x<<1)+1;
}
void upheap(int k)
{
	int key=h[k];
	while(k>1 && d[key]<d[h[father(k)]])
	{
		h[k]=h[father(k)];
		inheap[h[k]]=k;
		k=father(k);
	}
	h[k]=key;
	inheap[h[k]]=k;
}
void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(left_son(k)<=nh)
		{
			son=left_son(k);
			if(right_son(k)<=nh && d[h[right_son(k)]]<d[h[son]])
				son=right_son(k);
			if(d[h[son]]>=d[h[k]])
				son=0;
		}
		if(son)
		{
			swap(h[k],h[son]);
			inheap[h[k]]=k;
			inheap[h[son]]=son;
			k=son;
		}
	}while(son);
}
inline void inapm(int k)
{
	for(int i=0,lim=a[k].sz(); i<lim; ++i)
	{
		int nod=a[k][i].fs;
		int cost=a[k][i].sc;
		if(d[nod]>cost)
		{
			t[nod]=k;
			d[nod]=cost;
			if(inheap[nod])
				upheap(inheap[nod]);
		}
	}
}
inline void citire()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	memset(d,127,sizeof(d));
	for(; m; --m)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x].pb(mp(y,z));
		a[y].pb(mp(x,z));
	}
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	d[1]=0;
	inapm(1);
	for(int i=2; i<=n; ++i)
	{
		h[++nh]=i;
		inheap[i]=nh;
		upheap(nh);
	}
	for(int i=1; i<n; ++i)
	{
		int k=h[1];
		inheap[k]=0;
		h[1]=h[nh--];
		inheap[h[1]]=1;
		downheap(1);
		inapm(k);
		r+=d[k];
		rez.pb(mp(t[k],k));
	}
	printf("%d\n",r);
	printf("%d\n",n-1);
	for(int i=0,lim=rez.sz(); i<lim; ++i)
		printf("%d %d\n",rez[i].fs,rez[i].sc);
	return 0;
}