#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
vector <pair <int, int> > graph[400001];
priority_queue <pair <int, pair<int, int> > > myheap;
vector <pair <int, int> > muchie;
int N, M;
int viz[200001];
ifstream fin("apm.in");
ofstream fout("apm.out");
int cost_min,nr_muchii;
void apm(int sursa)
{
	int cost;
	int lim = graph[sursa].size();
	for (int i = 0; i < lim; i++)
	{
		cost = graph[sursa][i].first;
		int index = graph[sursa][i].second;
		myheap.push(make_pair(-cost, make_pair(sursa,index)));
	}
	viz[sursa] = 1;
	while (!myheap.empty())
	{
		pair < int, pair<int, int> > p;
		p = myheap.top();
		myheap.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++;
			muchie.push_back(m);
			apm(m.second);
		}
	}

}
int main()
{
	int x, y, c;
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y >> c;
		graph[x].push_back(make_pair(c, y));
		graph[y].push_back(make_pair(c, x));
	}
	apm(1);
	fout << cost_min << endl << nr_muchii << endl;
	int l = muchie.size();
	for (int i = 0; i < l; i++)
		fout << muchie[i].first<<" "<<muchie[i].second<< endl;
	system("pause");
}