#include<fstream>
#include<vector>
#include<queue>
#define mmax 400100
#define nmax 200100
using namespace std;
vector <pair <int,int> > S;
int x[mmax],y[mmax],c[mmax],g[mmax],h[mmax];
void qs(int i, int j)
{
	int s=i,d=j,aux,piv=h[(i+j)>>1];
	while(s<=d)
	{
		while(c[h[s]]<c[piv])
			s++;
		while(c[h[d]]>c[piv])
			d--;
		if(s<=d)
		{
			aux=h[d];
			h[d]=h[s];
			h[s]=aux;
			s++;
			d--;
		}
	}
	if(i<d)
		qs(i,d);
	if(s<j)
		qs(s,j);
}
int main()
{
	int n,m,i,cx,cy,s=0;
	ifstream read ("apm.in");
	ofstream write ("apm.out");
	read>>n>>m;
	for(i=1;i<=m;i++)
	{
		read>>x[i]>>y[i]>>c[i];
		h[i]=i;
		if(i<=n)
			g[i]=i;
	}
	qs(1,m);
	for(i=1;i<=m&&S.size()<n-1;i++)
	{
		queue <int> Qx,Qy;
		cx=x[h[i]];
		cy=y[h[i]];
		while(cx!=g[cx])
		{
			Qx.push(cx);
			cx=g[cx];
		}
		while(cy!=g[cy])
		{
			Qy.push(cy);
			cy=g[cy];	
		}
		if(cx!=cy)
		{
			if(Qy.size()>Qx.size())
			{
				while(!Qy.empty())
				{
					g[Qy.front()]=cy;
					Qy.pop();
				}
				while(!Qx.empty())
				{
					g[Qx.front()]=cy;
					Qx.pop();
				}
				g[cx]=cy;
			}
			else
			{
				while(!Qx.empty())
				{
					g[Qx.front()]=cx;
					Qx.pop();
				}
				while(!Qy.empty())
				{
					g[Qy.front()]=cx;
					Qy.pop();
				}
				g[cy]=cx;
			}
			S.push_back(make_pair(x[h[i]],y[h[i]]));
			s+=c[h[i]];
		}
	}
	write<<s<<'\n'<<n-1<<'\n';
	vector <pair <int,int> > :: iterator el;
	for(el=S.begin();el!=S.end();el++)
		write<<(*el).first<<' '<<(*el).second<<'\n';
	return 0;
}