#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;
struct graph{ int mass; int v1; int v2; };
bool comp(const graph &a,const graph &b)
{
 return (a.mass < b.mass);
}

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

int main()
{

	//freopen("amp.in", "r", stdin);
	//freopen("amp.out", "w", stdout);
	int m, n,sum=0,roads=0;
	fin >> n >> m;
	vector<int>mst_1;
	vector<int>mst_2;
	vector<graph>g;
	for (int i = 0; i < m; i++)
	{
	graph l;
	fin >> 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);
		}
	}
	fout << sum << endl;
	fout << roads << endl;
	for (int i = 0; i < roads; i++){ fout << mst_1[i] << " " << mst_2[i] << endl; }

}