//Prim's Algorithm
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstdio>
using namespace std;

int n,m;
int hashMMM[500000];

struct edge{
  int x,y,c;
};

struct node{

  int y,c;
};

struct order{

  bool operator() (edge const &a, const edge &b){
    return a.c > b.c;
  }

};


vector<node>v[200001];
priority_queue<edge, vector<edge>, order> Q;
queue <edge> sol;
void debug(){

  for(unsigned int i = 1; i <= n; i++){
    cout << endl << i << endl;
    for(unsigned int j =0 ; j< v[i].size();j++)
     cout <<  "       " << v[i][j].y << " " <<  v[i][j].c << endl ;

  }
}

void scan(){

  scanf("%d %d",&n,&m);
  for(int i = 0 ; i < m; i++){
    int x,y,cost;
    scanf("%d %d %d",&x,&y,&cost);
    node current;
    current.y =y;
    current.c = cost;
    v[x].push_back(current);
    swap(x,current.y);
    v[x].push_back(current);
  }
  //debug();

}

void addEdge(int currentNode){

  for(unsigned int i = 0 ; i <  v[currentNode].size(); i++){
    if(hashMMM[v[currentNode][i].y] != 0)
      continue;
    edge K;
    K.x = currentNode;
    K.y = v[currentNode][i].y;
    K.c = v[currentNode][i].c;
    Q.push(K);

  }

}

void show(edge K){

  cout << K.x << " " << K.y << " " << K.c << endl;
}
void solve(){

  int cost = 0;
  int currentNode = 1;
  hashMMM[currentNode]++;
  addEdge(currentNode);

  while(!Q.empty()){

    edge K = Q.top();

    Q.pop();
    if(hashMMM[K.y] == 0){
    hashMMM[K.y]++;
    sol.push(K);
    currentNode = K.y;
    cost += K.c;
    addEdge(currentNode);
    }

  }
  printf("%d\n%d\n",cost,sol.size());
  while(!sol.empty()){

    edge K = sol.front();
    sol.pop();
    printf("%d %d\n",K.x,K.y);

  }
}

int main(){

  freopen("apm.in","r",stdin);
  freopen("apm.out","w",stdout);
  scan();
  solve();
  return 0;
}