#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 2e5 + 7;

struct edge
{
	int x, y, c;
};

bool cmp(edge a, edge b)
{
	return a.c < b.c;
}

vector <edge> edges;

int to[DIM];
int Rank[DIM];

void unite(int x, int y)
{
	if(Rank[x] > Rank[y])
		to[y] = x;
	else
		to[x] = y;
	
	if(Rank[x] == Rank[y])
		Rank[y]++;
}

int find(int nod)
{
	int i;
	
	for(i = nod; to[i] != i; i = to[i]);
	for(; to[nod] != nod;)
	{
		int y = to[nod];
		to[nod] = i;
		nod = y;
	}
	
	return i;
}

vector <pair <int, int> > v;

int main()
{
	int n, m;
	in >> n >> m;
	
	for(int i = 1; i <= m; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		
		edges.push_back(edge{x, y, c});
	}
	
	sort(edges.begin(), edges.end(), cmp);
	
	for(int i = 1; i <= n; i++)
	{
		to[i] = i;
		Rank[i] = 1;
	}
	
	int cost = 0;
	
	for(int i = 0; i < edges.size(); i++)
	{
		int x = edges[i].x;
		int y = edges[i].y;
		int c = edges[i].c;
		
		if(find(x) != find(y))
		{
			unite(find(x), find(y));
			
			v.push_back({x, y});
			
			cost += c;
		}
	}
	
	out << cost << '\n' << n - 1 << '\n';
	
	for(auto i : v)
		out << i.first << ' ' << i.second << '\n';
}