#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 200005
vector <pair<int, int> > s;
int cost,n,m,rang[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;
  }
}

int find(int x){
  if(rang[x]==x) return x;
  rang[x]=find(rang[x]);
  return rang[x];
}

void unite(int i, int j){
  rang[find(i)]=find(j);
}

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

void solve(){
  for(int i=1; i<=n; i++)
    rang[i]=i;
    sort(ind+1, ind+1+m, cmp);
    for(int i=1; i<=m; 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]];
        }
    cout<<cost<<'\n'<<n-1<<'\n';
    for(int i=0; i<n-1; i++)
      cout<<s[i].first<<' '<<s[i].second<<'\n';
}

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