# include <fstream>
# 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]]=k/2;
			k/=2;
		}
}


int main ()
{
	int x, y, c;
	ifstream fin ("apm.in");
	ofstream fout ("apm.out");
	fin>>n>>m;
	for (int i=1;i<=n;i++)
		a[i]=NULL;
	for (int i=1;i<=m;i++)
	{
		fin>>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;
	for (nod*p=a[start];p;p=p->next)
	{
		d[p->capat]=p->cost, t[p->capat]=start;
		nh++;
		h[nh]=p->capat;
		poz[p->capat]=nh;
		promoveaza(nh);
	}
	d[0]=infinit;
	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;
				if (poz[p->capat]>0)
					promoveaza (poz[p->capat]);
				else
				{
					nh++;
					h[nh]=p->capat;
					poz[p->capat]=nh;
					promoveaza(nh);
				}
			}
	}
	fout<<cost_t<<endl<<n-1<<endl;
	for (int i=1;i<=n;i++)
		if (t[i])
			fout<<i<<" "<<t[i]<<endl;
	return 0;
}