#include <fstream>
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)
      {
        return A.first > B.first;
      }
};


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;
}