# include <cstdio>
# include <cassert>
# include <iostream>
# define infinit 1<<30
using namespace std;
struct nod{
	int capat, cost;
	nod *next;};
int n, m, t[200003], d[200002], v[200002], h[200003], poz[200002], nh;
nod *a[200003];

void ad_muchie (int i,int j,int c)
{
	nod *q;
	q=new nod;
	q->capat=j,  q->cost=c;
	q->next=a[i];
	a[i]=q;
}	

void cerne (int k, int n)
{
	int i, eh=0;
	while (!eh && 2*k<=n)
	{
		i=2*k;
		if (i+1<=n && d[h[i+1]]<d[h[i]])
			i++;
		if (d[h[k]]<=d[h[i]])
			eh=1;
		else
		{
			int a;
			a=h[i], h[i]=h[k], h[k]=a;
			poz[h[k]]=k;
			poz[h[i]]=i;
			k=i;
		}
	}
}

void promoveaza (int k)
{
	int eh=0;
	while (!eh && k/2)
		if (d[h[k]]>=d[h[k/2]])
			eh=1;
		else
		{
			int a;
			a=h[k], h[k]=h[k/2], h[k/2]=a;
			poz[h[k]]=k;
			poz[h[k/2]]=k/2;
			k/=2;
		}
}


int main ()
{
	int x, y, c;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1;i<=n;i++)
		a[i]=NULL;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d", &x, &y, &c);
		ad_muchie(x, y, c);
		ad_muchie(y, x, c);
	}
	int start=1;
	for (int i=1;i<=n;i++)
		v[i]=0, t[i]=-1, d[i]=infinit, h[i]=i, poz[i]=i;
	nh=n;
	h[start]=h[nh];
	poz[h[start]]=start;
	nh--;
	cerne(start, nh);
	for (nod*p=a[start];p;p=p->next)
	{
		d[p->capat]=p->cost, t[p->capat]=start;
		promoveaza(poz[p->capat]);
	}
	v[start]=1, t[start]=0, d[start]=0;
	int cost_t=0;
	for (int i=1;i<n;i++)
	{
		int pmin=0;
		pmin=h[1];
		v[pmin]=1;
		cost_t+=d[pmin];
		h[1]=h[nh];
		poz[h[1]]=1;
		nh--;
		cerne(1, nh);
		for (nod *p=a[pmin];p;p=p->next)
			if (v[p->capat]==0 && d[p->capat]>p->cost)
			{	
				d[p->capat]=p->cost, t[p->capat]=pmin;
				promoveaza (poz[p->capat]);
			}
	}
	printf("%d\n%d\n", cost_t , n-1);
	for (int i=1;i<=n;i++)
		if (t[i])
			printf("%d %d\n", i, t[i]);
	return 0;
}