#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 200000
#define MAX_M 400000
#define INF 1e9
struct g{
  int b,cost;
};
int n,m;
int index[MAX_N];
int rez[MAX_N];
vector <g> graph[MAX_N];
g heap[MAX_N];
int s;

inline parent(int x){return (x-1)/2;}
inline leftc(int x){return x*2+1;}
inline rightc(int x){return x*2+2;}

void upHeap(int i){
  if(i && heap[parent(i)].cost>heap[i].cost){
    swap(heap[i],heap[parent(i)]);
    index[heap[i].b]=i;
    index[heap[parent(i)].b]=parent(i);
    upHeap(parent(i));
  }
}

void downHeap(int i){
  int left,right,smallest=i;
  left=leftc(i);
  right=rightc(i);
  if(left<s && heap[left].cost<heap[smallest].cost)
    smallest=left;
  if(right<s && heap[right].cost<heap[smallest].cost)
    smallest=right;
  if(smallest!=i){
    swap(heap[i],heap[smallest]);
    index[heap[i].b]=i;
    index[heap[smallest].b]=smallest;
    downHeap(smallest);
  }
}

void insertHeap(int i,int c){
  heap[s]={i,c};
  index[i]=s;
  upHeap(s++);
}

void eraseHeap(int node){
  int i;
  i=index[node];
  heap[i]=heap[s-1];
  index[node]=-1;
  index[heap[i].b]=i;
  s--;
  downHeap(i);
  upHeap(i);
}

void updateHeap(int node,int c){
  int i;
  i=index[node];
  heap[i].cost=c;
  upHeap(i);
  downHeap(i);
}

inline bool isInHeap(int node){return index[node]!=-1;}
inline g& findInHeap(int node){return heap[index[node]];}
inline g& topHeap(){return heap[0];}
inline bool isEmptyHeap(){return s==0;}


int main(){
  FILE *fin,*fout;
  int i,sum,a,b,cost;
  g top;
  fin=fopen("apm.in","r");
  fout=fopen("apm.out","w");
  fscanf(fin,"%d%d",&n,&m);

  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&a,&b,&cost);
    a--,b--;
    graph[a].push_back({b,cost});
    graph[b].push_back({a,cost});
  }

  insertHeap(0,0);
  for(i=1;i<n;i++){
    insertHeap(i,INF);
  }

  sum=0;

  while(!isEmptyHeap()){
    top=topHeap();
    eraseHeap(top.b);
    sum+=top.cost;
    for(g e:graph[top.b])
      if(isInHeap(e.b) && findInHeap(e.b).cost>e.cost){
        rez[e.b]=top.b;
        updateHeap(e.b,e.cost);
      }
  }

  fprintf(fout,"%d\n%d\n",sum,n-1);
  for(i=1;i<=n-1;i++){
    fprintf(fout,"%d %d\n",rez[i]+1,i+1);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}