#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
int n,m;
vector<int> ind;
int TT[200010],RG[200010];
typedef struct muchie
{
	int x,y,c;
};
muchie vec[400005];

int cost=0,nr=0;


bool cmp(muchie a,muchie b)
{
	if(a.c<b.c) return 1;
	return 0;
}

int find(int x)
{
	int R,y;
	for(R=x;R!=TT[R];R=TT[R]);
	
	for(;x!=TT[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;
	else TT[x]=y;
	
	if(RG[x]==RG[y]) RG[y]++;
}

void read()
{
	in>>n>>m;
	for(int i=1;i<=m;i++)
		in>>vec[i].x>>vec[i].y>>vec[i].c;
}
void solve()
{
	sort(vec+1,vec+m+1,cmp);
	int k=n;
	for(int i=1;i<=m;i++)
	{
		TT[i]=i;
		RG[i]=1;
	}
	int x,y;
	for(int i=1;i<=m;i++)
	{
		x=find(vec[i].x);
		y=find(vec[i].y);
		if(x!=y)
		{
			k--;
			unite(x,y);
			nr++;
			ind.push_back(i);
			cost+=vec[i].c;
		}
		if(k==1)return ;
	}
}

int main()
{
	read();
	solve();
	out<<cost<<"\n"<<nr<<"\n";
	vector<int>::iterator it;
	for(it=ind.begin();it!=ind.end();it++)
	{
		out<<vec[*it].x<<" "<<vec[*it].y<<"\n";
	}
}