#include<cstdio>
#include<vector>
#include<bitset>

using namespace std;

int i,j,n,m,h[400000],unde[200010],cine[200010],v[200010],nr,rez;

vector<pair<int,int> >a[200010];
bitset<200010> fol;

inline void inter(int &a,int &b)
{
	int aux=a;
	a=b;
	b=aux;
}

void upheap(int poz)
{
	while(poz>1&&v[h[poz]]<v[h[poz/2]])
	{
		inter(unde[h[poz]],unde[h[poz/2]]);
		inter(h[poz],h[poz/2]);
		
		poz/=2;
	}
}

void downheap(int poz)
{
	while((poz*2<=nr&&v[h[poz]]>v[h[poz*2]])||(poz*2+1<=nr&&v[h[poz]]>v[h[poz*2+1]]))
	{
		if(v[h[poz*2]]<v[h[poz*2+1]])
		{
			inter(unde[h[poz]],unde[h[poz*2]]);
			inter(h[poz],h[poz*2]);
			poz=poz*2;
		}
		else 
		{
			inter(unde[h[poz]],unde[h[poz*2+1]]);
			inter(h[poz],h[poz*2+1]);
			poz=poz*2+1;
		}
	}
}

void afis(int a[])
{
	for(int i=1;i<=20;++i) printf("%d ",v[a[i]]);
	printf("\n\n");
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	for(i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		
		a[x].push_back(make_pair(y,z));
		a[y].push_back(make_pair(x,z));
	}
	
	h[++nr]=1;
	unde[1]=nr;
	v[0]=1000000000;
	
	for(i=2;i<=n;++i)
	{
		h[++nr]=i;
		unde[i]=nr;
		v[i]=1000000000;
	}
	
	for(i=1;i<=n;++i)
	{
		int u=h[1];
		fol[u]=1;
		
		h[1]=h[nr];
		h[nr]=0;
		nr--;
		unde[h[1]]=1;
		downheap(1);
		
		rez+=v[u];
		
		for(j=0;j<a[u].size();++j)	if(!fol[a[u][j].first])
		{
			int fiu=a[u][j].first;
			int cost=a[u][j].second;
			
			if(v[fiu]>cost)
			{
				v[fiu]=cost;
				cine[fiu]=u;
				upheap(unde[fiu]);
			}
		}
	}
	
	printf("%d\n%d\n",rez,n-1);
	
	for(i=2;i<=n;++i) printf("%d %d\n",i,cine[i]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}