#include<fstream>
#define p push_back
#define mp make_pair
#define fi first
#define se second
#define NM 200100
#define inf (1<<30)
#include<vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair<int,int> > v[NM];
int T[NM],H[NM],P[NM],S,D[NM],L,d,y,c,m,x,i,n;
bool viz[NM];
void urca(int po)
{
	while((po>>1)&&D[H[po]]<D[H[po>>1]])
	{
		swap(H[po],H[po>>1]);
		swap(P[H[po]],P[H[po>>1]]);
		po>>=1;
	}
}
void coboara(int po)
{
	y=-1;
	while(y!=po)
	{
		y=po;
		if((y<<1)<=L&&D[H[y<<1]]<D[H[po]])
			po=y<<1;
		if((y<<1)+1<=L&&D[H[(y<<1)+1]]<D[H[po]])
			po=(y<<1)+1;
		swap(H[po],H[y]);
		swap(P[H[po]],P[H[y]]);
	}
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>c;
		v[x].p(mp(y,c));
		v[y].p(mp(x,c));
	}
	for(i=1;i<=n;++i)
		D[i]=inf;
	D[1]=-inf;
	H[++L]=1;
	P[1]=1;
	for(i=2;i<=n;++i)
		H[i]=i,P[i]=i,viz[i]=1;
	L=n;
	viz[1]=1;
	while(L)
	{
		x=H[1];
		P[x]=0;
		H[1]=H[L--];
		coboara(1);
		for(i=0;i<v[x].size();++i)
		{
			d=v[x][i].fi;
			c=v[x][i].se;
			if(c<D[d]&&P[d])
			{
				D[d]=c;
				T[d]=x;
				urca(P[d]);
			}
		}
	}
	for(i=2;i<=n;++i)
		S+=D[i];
	g<<S<<"\n"<<n-1<<"\n";
	for(i=1;i<=n;++i)
		if(T[i])
			g<<T[i]<<" "<<i<<"\n";
	return 0;
}