#define NDEBUG   // NDEBUG definita nella versione che consegno
#include <cassert>
#ifndef NDEBUG
#include <iostream>  // uso di cin e cout non consentito in versione finale
#endif
#include <fstream>
#include <string>
#include <deque>
#include <stdio.h>
#include <queue>

using namespace std;

class edge
{
public:
    unsigned int weight;
    unsigned int target;
    unsigned int origin;
};

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const edge& lhs, const edge&rhs) const
  {
    if (reverse) return (lhs.weight<rhs.weight);
    else return (lhs.weight>rhs.weight);
  }
};




int main()
{
    int m, n;
    deque<deque<edge> > graph;
    ifstream fin("input.txt"); assert( fin );
    fin >> n >> m;
    graph.resize(n);
    for(unsigned int i = 0; i < m; i++)
    {
        unsigned int origin, destination, weight;
        fin >> origin >> destination >> weight;
        edge newEdge;
        newEdge.origin = origin-1;
        newEdge.weight = weight;
        newEdge.target = destination-1;
        graph.at(origin-1).push_back(newEdge);
        graph.at(destination-1).push_back(newEdge);
    }

    deque<edge> path;

    int startNode = 0;
    vector<bool> covered(n, false);    

    edge initial;
    int weight = 0;
    {
        priority_queue<edge, vector<edge>, mycomparison> data;


        for(unsigned int i = 0; i < graph.size(); i++)
        {
            for(unsigned int y = 0; y < graph[i].size(); y++)
                data.push(graph[i][y]);
        }

        // take a first edge
        initial = data.top(); data.pop();
        covered[initial.target] = true;
        covered[initial.origin] = true;
    }

    path.push_back(initial);
    weight += initial.weight;

        priority_queue<edge, vector<edge>, mycomparison> data;
        for(unsigned int i = 0; i < graph[initial.origin].size(); i++)
        {
                data.push(graph[initial.origin][i]);
        }

        for(unsigned int i = 0; i < graph[initial.target].size(); i++)
        {
                data.push(graph[initial.target][i]);
        }
    
    while(!data.empty())
    {
                    edge testing = data.top(); data.pop();
        if((covered[testing.origin] == true && covered[testing.target] == false) || (covered[testing.origin] == false && covered[testing.target] == true))
        {
            path.push_back(testing);
            weight +=testing.weight;

            int node;
            if(covered[testing.origin] == true)
                node = testing.target;
            else    
                node = testing.origin;
            covered[testing.origin] = true;
            covered[testing.target] = true;
            // add the new reacheable nodes.
        for(unsigned int i = 0; i < graph[node].size(); i++)
        {
                data.push(graph[node][i]);
        }
        }
    }

  ofstream fout("output.txt"); assert( fout );
  fout << weight << endl;
  for(unsigned int i = 0; i < path.size(); i++)
  {
    fout << path[i].origin+1 << " " << path[i].target+1 << endl;
  }
  fout.close();

    }