#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, int> &A, const pair<int, int> &B) const
      {
        if ( A.first > B.first ) return 1;
		return 0;
      }
};
 
 
int N, M, dad[NMAX], co[NMAX];
vector< pair<int, int> > A[NMAX];
bool ap[MMAX];
priority_queue< pair<int, int>, vector< 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(make_pair(0, 1));
      co[1] = 0;
      ap[0] = true;
      for (int ii = 1; ii <= N; ++ii)
      {
            int nod = 0, cost = 0;
        while (ap[nod])
        {
            cost = PQ.top().first;
            nod = PQ.top().second;
            PQ.pop();
        }
        //mc += co[nod];
            mc += cost;
            ap[nod] = true;
             
            for (vector< pair<int, int> >::iterator it = A[nod].begin(); it != A[nod].end(); ++it)
            {
                  if (!ap[it->second] && it->first < co[it->second])
            {
                co[it->second] = it->first;
                dad[it->second] = nod;
                PQ.push(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;
}