#include<fstream>
#include<algorithm>
#include<vector>
#define maxn 200005
#define maxm 400005
using namespace std;
int x[maxm],y[maxm],c[maxm],indx[maxm],a[maxn],r[maxn],n,m,ct,x1,y1;
vector<int> rez;

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

bool cmp(int x, int y){
  if(c[x]<c[y])
    return 1;
  return 0;
}

void unite(int x,int y){
  if(r[x]>r[y])
    a[x]=y;
  else a[y]=x;
    if(r[x]==r[y])
      r[x]++;
}

int find(int x){
  int r,aux;
  for(r=x; r!=a[r]; r=a[r]);
  while(a[x]!=x){
    aux=a[x];
    a[x]=r;
    x=aux;
  }
return r;
}

int main(){
  cin>>n>>m;
  for(int i=1; i<=n; i++)
    a[i]=i, r[i]=1;
  for(int i=1; i<=m; i++)
    cin>>x[i]>>y[i]>>c[i], indx[i]=i;
  sort(indx+1, indx+m+1,cmp);
  for(int i=1; i<=m; i++){
    x1=find(x[indx[i]]); y1=find(y[indx[i]]);
    if(x1!=y1){
      unite(x1,y1);
      ct+=c[indx[i]];
      rez.push_back(indx[i]);
    }
  }
  cout<<ct<<'\n'<<n-1<<'\n';
  for(int i=0; i<n-1; i++)
    cout<<x[rez[i]]<<' '<<y[rez[i]]<<'\n';
  return 0;
}