#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct nod
{
	int x, y, cost;

	friend bool operator <(const nod& a, const nod& b)
	{
		return a.cost < b.cost;
	}
};

const int NMAX = 2*1e5 + 1;
const int MMAX = 4*1e5 + 1;

int n, m;
nod v[MMAX];
int tata[NMAX];

int sef(int x)
{
	if (tata[x] == x)
		return x;
	return tata[x] = sef(tata[x]);
}

void unire(int x, int y)
{
	int sefx = sef(x);
	int sefy = sef(y);
	tata[sefy] = sefx;
}

int main()
{
	in>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int x, y, cost;
		in>>x>>y>>cost;
		v[i].x = x;
		v[i].y = y;
		v[i].cost = cost;
	}
	for(int i=1; i<=n; i++)
	{
		tata[i] = i;
	}
	sort(v+1, v+m+1);

    int s=0, i=1;
	vector<nod> sol;

	while(sol.size() < n-1)
	{
		int x = v[i].x;
		int y = v[i].y;
		if(sef(x) != sef(y))
		{
			unire(x, y);
			s += v[i].cost;
			sol.push_back(v[i]);
		}
		i++;
	}

	out<<s<<"\n"<<sol.size()<<"\n";
	for(i=0; i<sol.size(); i++)
	{
		out<<sol[i].x<<" "<<sol[i].y<<"\n";
	}
    return 0;
}