#include<fstream>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;


#define MAX 200010
//#define _DEBUG

int unionSet[MAX];

int GetRoot(int x)
{
	if(unionSet[x] == 0)
	{
		return x;
	}
	else
	{
		unionSet[x] = GetRoot(unionSet[x]);
	}

	return unionSet[x];
}

bool Add(int x, int y)
{
	int rX = GetRoot(x);
	int rY = GetRoot(y);

	if(rX == rY)
	{
		return false;
	}

	unionSet[rX] = rY;

	return true;
}

struct Edge
{
	int x, y, c, id;
};

vector<Edge> edges;
int main()
{
	int n,m;

	#ifndef _DEBUG
		ifstream in("apm.in");
		ofstream out("apm.out");

		cin.rdbuf(in.rdbuf());
		cout.rdbuf(out.rdbuf())
		
	#endif 

	cin>>n>>m;

	for(int i=1;i<=m;++i)
	{
		int x,y,c;

		cin>>x>>y>>c;

		edges.push_back({x,y,c,i});		
	}

	sort(edges.begin(), edges.end(), [](const Edge &e1, const Edge &e2){return e1.c < e2.c;});

	int result = 0;

	vector<Edge> resultEdges;

	for(int i=0;i<edges.size();++i)
	{
		if(Add(edges[i].x, edges[i].y))
		{
			result+=edges[i].c;
			resultEdges.push_back(edges[i]);
		}
	}

	cout << result<<"\n";

	cout << resultEdges.size()<<"\n";

	for(int i=0;i<resultEdges.size();++i)
	{
		cout<<resultEdges[i].x << " "<< resultEdges[i].y <<"\n";
	}
	
	return 0;
}