#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,pair<int,int> > > M;
vector<pair<int,int> > SOL;
int n,m,a,b,c,COST,i,dad[200010];
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)dad[i]=i;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		M.push_back(make_pair(c,make_pair(a,b)));
	}
	sort(M.begin(),M.end());
}
void solve()
{
	for(vector<pair<int,pair<int,int> > >::iterator it=M.begin();it!=M.end();it++)
	{
		c=(*it).first;
		a=(*it).second.first;
		b=(*it).second.second;
		SOL.push_back(make_pair(b,a));
		while(a!=dad[a])a=dad[a];
		while(b!=dad[b])b=dad[b];
		if(a!=b){COST+=c;if(a<b)dad[b]=a; else dad[a]=b;} else SOL.pop_back();
	}
	printf("%d\n",COST);
	printf("%d\n",SOL.size());
	for(vector<pair<int,int> >::iterator it=SOL.begin();it!=SOL.end();it++)
		printf("%d %d\n",(*it).first,(*it).second);
}