// All rights reserved to me ..
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define NMAX 200100
#define MMAX 400100
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");


struct cmp
{
      bool operator()(const pair<int, pair<int, int> > &A, const pair<int, pair<int, int> > &B)
      {
		return A.second.first > B.second.first;
      }
};
inline pair< int, pair<int, int> > fct(int nr, pair<int, int> ret)
{
	pair< int, pair<int, int> > masa; // cu diacritice
	masa.first = nr;
	masa.second = ret;
	return masa;
}

int N, M, dad[NMAX], co[NMAX];
vector< pair<int, int> > A[NMAX];
bool ap[MMAX];
priority_queue< pair< int, pair<int, int> >, vector< pair< int, pair<int, int> > >, cmp> PQ;
      int mc = 0;

int main()
{
      for (int i = 1; i < NMAX; ++i) co[i] = 2000000000;
	
      fin >> N >> M;
	for (int i = 1; i <= M; ++i)
      {
            int X, Y, cost;
            fin >> X >> Y >> cost;
            
            A[X].push_back(make_pair(cost, Y));
            A[Y].push_back(make_pair(cost, X));
      }
	
      PQ.push(fct(0, make_pair(0, 1)));
      co[1] = 0;
      ap[0] = true;
      for (int ii = 1; ii <= N; ++ii)
      {
		int nod = 0, cost = 0, tacsu = 0;
		while (ap[nod])
		{
			cost = PQ.top().second.first;
			nod = PQ.top().second.second;
			tacsu = PQ.top().first;
			PQ.pop();
		}
		mc += cost;
		ap[nod] = true;
		dad[nod] = tacsu;
		
		for (vector< pair<int, int> >::iterator it = A[nod].begin(); it != A[nod].end(); ++it)
		{
			if (!ap[it->second])
			{
				PQ.push(fct(nod, make_pair(it->first, it->second)));
			}
		}
	}
      
      fout << mc << '\n';
      fout << N - 1 << '\n';
	
      for (int i = 2; i <= N; ++i)
      {
		fout << i << ' ' << dad[i] << '\n';
      }
      
      fout.close();
      return 0;
}