#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
vector <pair <int, int> > graph[400001];
priority_queue <pair <int, pair<int, int> > > mh;
vector <pair <int, int> > muchii;
int n, m;
int viz[200001];

int cost_min,nr_muchii;
void Prim(int s)
{
    int l=graph[s].size();
	int cost;
	for (int i = 0; i < l; i++)
	{

		cost = graph[s][i].first;
		int index = graph[s][i].second;
		mh.push(make_pair(-cost, make_pair(s,index)));
	}
	viz[s] = 1;
	while (!mh.empty())
	{
		pair < int, pair<int, int> > p;
		p = mh.top();
		mh.pop();
		pair <int, int> m = p.second;
		cost = -p.first;
		if (viz[m.second] != 1 || viz[m.first]!=1)
		{
			cost_min =cost_min+cost;
			nr_muchii++;
			muchii.push_back(m);
			Prim(m.second);
		}
	}
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
	int x, y, c;
	in >> n >> m;
	for (int i = 0; i < m; i++)
	{
		in >> x >> y >> c;
		graph[x].push_back(make_pair(c, y));
		graph[y].push_back(make_pair(c, x));
	}
	Prim(1);
	out << cost_min << endl << nr_muchii << endl;
	int l=muchii.size();
	for (int i = 0; i < l; i++)
		out << muchii[i].first<<" "<<muchii[i].second<< endl;
}