#include<fstream>
#include<vector>

#define NMAX 200005
#define MMAX 500005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Edges
{
	int x,y,z;
}v[NMAX];

vector<int> Sort[2005],sol;
int n,m,T[NMAX],ind[NMAX],nr;

inline int tree(int nod)
{
	if(T[nod]!=nod)
		T[nod]=tree(T[nod]);
	return T[nod];
}

int main()
{
	fin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fin>>v[i].x>>v[i].y>>v[i].z;
		Sort[v[i].z+1000].push_back(i);
	}
	for(size_t i=0,k=1;i<2005;i++)
		for(size_t j=0;j<Sort[i].size();j++)
			ind[k++]=Sort[i][j];
	for(int i=1;i<=n;i++)
		T[i]=i;
	for(int i=1;i<=m;i++)
		if(tree(v[ind[i]].x)!=tree(v[ind[i]].y))
		{
			T[tree(v[ind[i]].x)]=tree(v[ind[i]].y);
			nr+=v[ind[i]].z;
			sol.push_back(ind[i]);
		}
	fout<<nr<<'\n'<<n-1<<'\n';
	for(size_t i=0;i<sol.size();i++)
		fout<<v[sol[i]].x<<' '<<v[sol[i]].y<<'\n';
	return 0;
}