//prim
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <set>
using namespace std;

int main()
{
	int n, m, x, y, c;
	vector<int> pred, d;
	vector<bool> viz;
	vector< list< pair<int,int> > > L;
	list< pair<int,int> > APCM;
	ifstream in("apm.in");
	ofstream out("apm.out");

	in >> n >> m;
	pred.resize(n+1);
	d.resize(n+1,1000);
	L.resize(n+1);
	viz.resize(n+1, false);

	for ( int i = 0; i< m; i++ )
	{
		in >> x >> y >> c;
		L[x].push_back( make_pair(c,y) );
		L[y].push_back( make_pair(c, x) );
	}

	set< pair<int, int> > q;
	d[1] = 0;
	pred[1] = 0;
	q.insert( make_pair(0,1) );

	int cost = 0;

	while( !q.empty() )
	{
		pair<int,int> p = *q.begin();
		q.erase(q.begin());

		int nod = p.second;
		if ( viz[nod] == false )
		{
			viz[nod] = true;
			if ( pred[nod] != 0 )
			{
				APCM.push_back( make_pair(nod, pred[nod]));
				cost+=p.first;
			}
			for ( pair<int,int> i : L[nod] )
				if ( !viz[i.second] )
				{
					if( i.first < d[i.second] )
					{
						d[i.second] = i.first;
						pred[i.second] = nod;
						q.insert(i);	
					}
					
				}
		}
	}
	out <<cost<<'\n';
	out << APCM.size()<<'\n';
	for ( auto i: APCM )
		out<<i.first<<' '<<i.second<<'\n';
	in.close();
	out.close();
	return 0;
}