#include<fstream>
#include<vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N=200010;
int n,m,t[N];
struct nod{	int x,y,c;};
nod v[N];
void read()
{
	in>>n>>m;
	for(int i=1;i<=n;i++)
		t[i]=i;//init
	
	for(int i=1;i<=m;i++)
		in>>v[i].x>>v[i].y>>v[i].c;
}
bool cmp( nod a, nod b)
{
	return (a.c < b.c);
}

void compresie(int x)
{
	if(t[x]==x)
		return ;
	compresie(t[x]);
	t[x]=t[t[x]];
}
void solve()
{
	vector<int>sau;
	
	int q,w,sum=0;
	
	sort(v+1,v+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		q=v[i].x;
		w=v[i].y;
		compresie(q);
		compresie(w);
		if(t[q]==t[w])
			continue;
		
		sau.push_back(i);
		
		t[t[q]]=t[w];
		sum+=v[i].c;
	}
	out<<sum<<"\n"<<sau.size()<<"\n";
	for(int i=0;i<sau.size();i++)
		out<<v[sau[i]].x<<" "<<v[sau[i]].y<<"\n";
}
int main()
{
	read();
	solve();
	return 0;
}