#include <iostream> 
#include <cstdio>  
#include <vector>
#include <algorithm>
using namespace std;
struct graph{ int mass; int v1; int v2; };
bool comp(graph &a, graph &b)
{ 
 return (a.mass < b.mass); 
}
int main()
{
	freopen("amp.in", "r", stdin);
	freopen("amp.out", "w", stdout);
	int m, n,sum=0,roads=0;
	cin >> n >> m;
	vector<int>mst_1;
	vector<int>mst_2;
	vector<graph>g;
	for (int i = 0; i < m; i++)
	{
	graph l;
	cin >> l.v1 >>l.v2 >> l.mass;
	g.push_back(l);
	}
	sort(g.begin(), g.end(),comp);
	vector<int>tree(n);
	for (int i = 0; i < n; i++)
	{
	tree[i] = i;
	}
	for (int i = 0; i < m; i++)
	{
		int a = g[i].v1-1;
		int b = g[i].v2-1;
		if (tree[a] != tree[b])
		{ 
		int old = tree[a];
		int neu = tree[b];
		for (int j = 0; j < n;j++)
		 { 
		 if (tree[j] ==old){ tree[j] = neu; }
		 }
		sum += g[i].mass;
		roads++;
		mst_1.push_back(g[i].v1);
		mst_2.push_back(g[i].v2);
		}
	}
	cout << sum << endl;
	cout << roads << endl;
	for (int i = 0; i < roads; i++){ cout << mst_1[i] << " " << mst_2[i] << endl; }

}