#include <bits/stdc++.h>
using namespace std;
#define MAXM 400001
#define MAXN 200001

int dad[MAXN];
int find_daddy(int x){
  if(x==dad[x])
    return x;
  return dad[x]=find_daddy(dad[x]);
}
inline void join(int x, int y){
  int rx, ry;
  rx=find_daddy(x);
  ry=find_daddy(y);
  dad[ry]=rx;
}
bool check (int x, int y){
  int a, b;
  a=find_daddy(x);
  b=find_daddy(y);
  if(a==b)
    return 1;
  return 0;
}

struct edge{
  int nod1, nod2, cost;
};

edge v[MAXM];
bool cmp(edge a, edge b){
  if(a.cost<b.cost)
    return 1;
  return 0;
}
vector<int>sol;

int main(){
  FILE*fin=fopen("apm.in", "r");
  FILE*fout=fopen("apm.out", "w");
  int n, m, i, rez;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=m; i++)
    fscanf(fin, "%d%d%d", &v[i].nod1, &v[i].nod2, &v[i].cost);
  for(i=1; i<=n; i++)
    dad[i]=i;
  sort(v+1, v+m+1, cmp);
  i=1;
  rez=0;
  while(sol.size()<n-1){
//    printf("%d %d\n", v[i].nod1, v[i].nod2);
    if(check(v[i].nod1, v[i].nod2)==0){
      sol.push_back(i);
      rez+=v[i].cost;
      join(v[i].nod1, v[i].nod2);
    }
    i++;
  }
  fprintf(fout, "%d\n%d\n", rez, n-1);
  for(i=0; i<n-1; i++)
    fprintf(fout, "%d %d\n", v[sol[i]].nod1, v[sol[i]].nod2);
  return 0;
}