#include <bits/stdc++.h>
#define Nm 200005
#define Mm 400005

using namespace std;

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

struct per{
  int x;
  int y;
  int cost;
};

pair <int, int>v[Mm];
int n,m,t[Nm],k,S;
per a[Mm];

void citire(){
  in>>n>>m;
  for(int i=1;i<=m;i++)
    in>>a[i].x>>a[i].y>>a[i].cost;
  for(int i=1;i<=n;i++)
    t[i]=i;
}

bool cmp(per i, per j){
  if(i.cost<j.cost)
    return true;
  return false;
}

void marea_unire(int xx, int yy){
  for(int i=1;i<=n;i++)
    if(t[i]==xx)
      t[i]=yy;
}

void solve(){
  for(int i=1;i<=m;i++)
    if(t[a[i].x]!=t[a[i].y]){
      S+=a[i].cost;
      v[++k].first=a[i].x,v[k].second=a[i].y;
      marea_unire(t[a[i].x],t[a[i].y]);
    }
}

int main(){
  citire();
  sort(a+1,a+m+1,cmp);
  solve();
  out<<S<<'\n'<<k<<'\n';
  for(int i=1;i<=k;i++)
    out<<v[i].first<<' ' <<v[i].second <<'\n';
  return 0;
}