#include <fstream>
#include <map>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

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

struct edge{
  int x, y, c;
  const bool operator<(const edge& rhs) const {
    return c < rhs.c;
  }
  const bool operator>(const edge& rhs) const {
    return c > rhs.c;
  }
};

int main (int argc, char const *argv[])
{
  int n, m;
  priority_queue<edge, vector<edge>, greater<edge> > heap;
  map<int, bool> visited;
  map<int, vector<edge> > graph;
  vector<edge>::iterator it;


  in>>n>>m;
  edge initial;
  for(int i = 0; i < m; i++)
  {
    edge e;
    in>>e.x>>e.y>>e.c;

    graph[e.x].push_back(e);
    graph[e.y].push_back(e);

    if (i == 0) {
      initial = e;
    } else {
      if (e < initial) {
        initial = e;
      }
    }
  }

  int cost = initial.c;
  int count = 1;
  vector<edge> solution;
  visited[initial.x] = true;
  visited[initial.y] = true;
  solution.push_back(initial);


  for (it = graph[initial.x].begin(); it != graph[initial.x].end(); ++it) {
    heap.push(*it);
  }
  for (it = graph[initial.y].begin(); it != graph[initial.y].end(); ++it) {
    heap.push(*it);
  }


  while(!heap.empty() && visited.size() != n) {
    edge e = heap.top();
    heap.pop();
    if((visited[e.x] && visited[e.y]) || (!visited[e.x] && !visited[e.y]))
      continue;
    cost += e.c;
    count ++;
    solution.push_back(e);

    int newnode;

    if (!visited[e.x]) {
      visited[e.x] = true;
      newnode = e.x;
    } else {
      visited[e.y] = true;
      newnode = e.y;
    }

    for (it = graph[newnode].begin(); it != graph[newnode].end(); ++it) {
      heap.push(*it);
    }
  }

  out<<cost<<"\n"<<count<<"\n";

  for(it = solution.begin(); it != solution.end(); ++it){
    out<<(*it).x<<" "<<(*it).y<<"\n";
  }

  return 0;
}