#include<fstream>
#include<vector>
#include<set>
#define Nmax 200001
#define INF 20001 
using namespace std;
vector< pair<int, int> >G[Nmax];
set< pair<int, int> > cmin;

int viz[Nmax], p[Nmax], i, j, a, b, c, n, m;
int nrv, d[Nmax], cost;

void APM()
{
	int costmin, vfmin;
	set< pair<int, int> >::iterator it;
	nrv=n-1;
	while(nrv)
	{
		it=cmin.begin();
		costmin=(*it).first;
		vfmin=(*it).second;
		cost+=costmin;
		viz[vfmin]=1;
		nrv--;
		cmin.erase(make_pair(costmin, vfmin));
		for(i=0;i<G[vfmin].size();i++)
			if(!viz[G[vfmin][i].first] && G[vfmin][i].second<d[G[vfmin][i].first])
			{
				cmin.erase(make_pair(d[G[vfmin][i].first], G[vfmin][i].first));
				cmin.insert(make_pair(G[vfmin][i].second, G[vfmin][i].first));
				d[G[vfmin][i].first]=G[vfmin][i].second;
				p[G[vfmin][i].first]=vfmin;
			}
	}
}

int main()
{
	int Min=1001;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
		G[b].push_back(make_pair(a, c));
	}
	for(i=0;i<G[1].size();i++)
	{
		cmin.insert(make_pair( G[1][i].second, G[1][i].first));
		d[G[1][i].first]=G[1][i].second;
		p[G[1][i].first]=1;
	}
	for(i=1;i<=n;i++)
		if(!d[i])
			d[i]=INF;
	viz[1]=1;
	APM();
	printf("%d\n", cost);
	printf("%d\n", n-1);
	for(i=1;i<=n;i++)
		if(p[i]!=p[1])
		printf("%d %d\n", i, p[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}