#include<fstream> 
#include<algorithm> 
#define NMAX 200001 

using namespace std; 

ifstream in("apm.in"); 
ofstream out("apm.out"); 

int N, M, ind[NMAX], tata[NMAX], rang[NMAX]; 

struct muchie
{
	int x,y,c; 
}m[2*NMAX]; 

bool comp(const muchie &unu, const muchie &doi) 
{
	return unu.c < doi.c; 
}

int find(int nod) 
{
	int R; 
	for(R = nod; tata[R]!=R; R = tata[R]); 
	
	for(; nod != tata[nod]; ) 
	{
		tata[nod] = R; 
		nod = R; 
	}
	return R; 
}
void unite(int x, int y) 
{
	if(rang[x] > rang[y]) 
		tata[y] = x; 
	else tata[x] = y; 
	
	if(rang[x] == rang[y]) 
		rang[y] ++; 
}

int main() 
{
	int i, cost = 0, nr = 0; 
	in >> N >> M; 
	
	for(i = 1; i <= M; i++)
		in >> m[i].x >> m[i].y >> m[i].c;
	
	for(i = 1; i <= N; i++) 
		{
			tata[i] = i; 
			rang[i] = 1; 
	}
	
	sort(m+1,m+M+1,comp);
	
	for(i = 1; i <= M && nr < N; ) 
	{
		int t1 = find(m[i].x); 
		int t2 = find(m[i].y); 
		if(t1 != t2) 
		{
			ind[++nr] = i; 
			cost+=m[i].c; 
			unite(t1, t2); 
		}
		i++;
	}
	
	out << cost << '\n' << nr << '\n'; 
	
	for(i = 1; i <= nr; i++) 
		out << m[ind[i]].x << " " << m[ind[i]].y << '\n'; 
}