# 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];
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;
}	

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;
	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;
		for (int j=1;j<=n;j++)
			if (v[j]==0 && d[j]<d[pmin])
					pmin=j;
		v[pmin]=1;
		cost_t+=d[pmin];
		assert(pmin>0);
		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;
	}
	fout<<cost_t<<endl<<n-1<<endl;
	for (int i=1;i<=n;i++)
		if (t[i])
			fout<<i<<" "<<t[i]<<endl;
	return 0;
}