#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 200005
vector <pair<int, int> > s;
int cost,n,m,nr,rang[maxn],arb[maxn],c[maxn],x[maxn],y[maxn],ind[maxn];

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

void read(){
  cin>>n>>m;
  for(int i=1; i<=m; i++){
    cin>>x[i]>>y[i]>>c[i];
    ind[i]=i;
  }
}

void unite(int i, int j){
  if(rang[i]>rang[j])
    arb[j]=i;
  else arb[i]=j;
  if(rang[i]==rang[j])
    rang[j]++;
}

int find(int x){
  int r,y;
  for(r=x; arb[r]!=r; r=arb[r]);
  for(; arb[x]!=x; x=arb[x]){
    y=arb[x];
    arb[x]=r;
    x=y;
  }
  return r;
}

bool cmp(int i, int j){
    return(c[i]<c[j]);
}

void solve(){
  for(int i=1; i<=n; i++){
    rang[i]=1;
    arb[i]=i;
  }
    sort(ind+1, ind+1+m, cmp);
    for(int i=1; i<=m&&nr<n-1; i++)
        if(find(x[ind[i]])!=find(y[ind[i]])) {
          unite(x[ind[i]],y[ind[i]]);
          s.push_back(make_pair(x[ind[i]],y[ind[i]]));
          cost+=c[ind[i]];
          nr++;
        }
    cout<<cost<<'\n'<<nr<<'\n';
    for(int i=0; i<n-1; i++)
      cout<<s[i].first<<' '<<s[i].second<<'\n';
}

int main(){
  read();
  solve();
}