#include<fstream>
#include<vector>
#define oo (1<<30)
#define nmax 200100
using namespace std;
vector <pair <int,int> > v[nmax];
vector <int> s;
int d[nmax],h[nmax],hh[nmax];
int L;
void percolate(int nod)
{
	int safe=h[nod];
	while(nod>1&&d[h[nod>>1]]>d[safe])
	{
		hh[h[nod>>1]]=nod;
		h[nod]=h[nod>>1];
		nod>>=1;
	}
	hh[safe]=nod;
	h[nod]=safe;
}
int root()
{
	int safe=h[1];
	hh[h[L]]=1;
	h[1]=h[L--];
	int son,nod=1,ls,rs,aux;
	do
	{
		son=0;
		ls=(nod<<1);
		rs=1+ls;
		if(ls<=L)
		{
			son=ls;
			if(rs<=L&&d[h[rs]]<d[h[son]])
				son=rs;
			if(d[h[son]]>=d[h[nod]])
				son=0;
		}
		if(son)
		{
			hh[h[nod]]=son;
			hh[h[son]]=nod;
			aux=h[nod];
			h[nod]=h[son];
			h[son]=aux;
			nod=son;
		}
	}
	while(son);
	hh[safe]=0;
	return safe;
}	
int main()
{
	int n,m,i,x,y,cost,nod,S=0;
	ifstream read ("apm.in");
	ofstream write ("apm.out");
	read>>n>>m;
	while(m--)
	{
		read>>x>>y>>cost;
		v[x].push_back(make_pair(y,cost));
		v[y].push_back(make_pair(x,cost));
	}
	for(i=2;i<=n;i++)
	{
		d[i]=oo;
		h[i-1]=i;
		hh[i]=i-1;
	}
	s.push_back(1);
	L=n-1;
	vector <pair <int,int> > :: iterator fiu;
	for(fiu=v[1].begin();fiu!=v[1].end();fiu++)
	{
		d[(*fiu).first]=(*fiu).second;
		percolate(hh[(*fiu).first]);
	}
	while(L)
	{
		nod=root();
		S+=d[nod];
		s.push_back(nod);
		for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
			if(hh[(*fiu).first]&&d[(*fiu).first]>(*fiu).second)
			{
				d[(*fiu).first]=(*fiu).second;
				percolate(hh[(*fiu).first]);
			}		
	}		
	vector <int> :: iterator f;
	write<<S<<'\n'<<n-1<<'\n';
	for(f=s.begin()+1;f!=s.end();f++)
		write<<*f<<' '<<*(f-1)<<'\n';;
	return 0;
}