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

#define MAX 200010
//#define _DEBUG
priority_queue<pair<int,int>, vector<pair<int,int>>, std::greater<pair<int,int>>> pq;

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

vector<Edge> graph[MAX];

int Prim(int n, int s, vector<Edge> &resultEdges)
{
	vector<int> d(MAX + 1);
	vector<int> viz(MAX + 1);
	vector<Edge> edgeFather(MAX+1);
	for(int i=1;i<=n;++i)
	{
		d[i] = 1<<30;
		edgeFather[i].x = -1;
		viz[i] = 0;
	}

	d[s] = 0;

	pq.push({0,1});
	int total = 0;
	while(pq.size() > 0)
	{
		auto node = pq.top();
		pq.pop();
		viz[node.second] = 1;

		if(d[node.second] < node.first )
		{
			continue;
		}
		total+=node.first;
		for(auto& edge :graph[node.second])
		{
			if(d[edge.y] > edge.c && viz[edge.y] == 0)
			{
				d[edge.y] = edge.c;
				edgeFather[edge.y] = edge;
				pq.push({edge.c, edge.y});
			}
		}
	}

	for(int i=1;i<=n;++i)
	{
		if(edgeFather[i].x!=-1)
		{
			resultEdges.push_back(edgeFather[i]);
		}
	}

	return total;
}

int main()
{

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

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

	#endif
	int n,m;

	cin>>n>>m;

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

		cin>>x>>y>>c;

		graph[x].push_back({x,y,c,i});
		graph[y].push_back({y,x,c,i});
	}
	vector<Edge> resultEdges;
	int c = Prim(n, 1, resultEdges);

	cout << c<<"\n";

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

	for(auto& edge:resultEdges)
	{
		cout <<edge.x <<" "<<edge.y<<"\n";
	}
	
	return 0;
}