#include<fstream>
#include<algorithm>
#include<vector>
#define maxn 400010

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int RG[maxn],TT[maxn];
int ind[maxn];
int cnt;
typedef struct muchie 
{
	int x,y,cost;
};

muchie vec[maxn];

int find(int x)
{
	int R,y;
	for(R=x;TT[R]!=R;R=TT[R]);
	for(;TT[x]!=x;)
	{
		y=TT[x];
		TT[x]=R;
		x=y;
	}
	return R;
}

void unite(int x,int y)
{
	if(RG[x]>RG[y])
		TT[y]=x,RG[x]+=RG[y];
	else TT[x]=y,RG[y]+=RG[x];
	
}
		
bool cmp(muchie a, muchie b)
{
	if(a.cost<b.cost) return 1;
	return 0;
}

void read()
{
	int n,m;
	int x,y,z;
	in>>n>>m;
	for(int i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		cnt+=1;
		vec[cnt].x=x,vec[cnt].y=y,vec[cnt].cost=z;
		RG[i]=1;
		TT[i]=i;
	}
	sort(vec+1,vec+cnt+1,cmp);
}

int main()
{
	read();
	int cost=0,p,q,nr=0;
	for(int i=1;i<=cnt;i++)
	{
		p=vec[i].x;
		q=vec[i].y;
		if(find(p)!=find(q))
		{
			cost+=vec[i].cost;
			nr++,ind[nr]=i;
			unite(find(p),find(q));
		}
	}
	out<<cost<<"\n"<<nr;
	for(int i=1;i<=nr;i++)
		out<<vec[ind[i]].x<<" "<<vec[ind[i]].y<<"\n";
}