#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 200005
#define def vector<int>::iterator
vector <pair<int, int> > v[maxn], s;
int cost,n,m,rang[maxn],arb[maxn];

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

void read(){
  cin>>n>>m;
  int x,y,c;
  while(m){
    cin>>x>>y>>c;
    if(y>x)
    v[y].push_back(make_pair(c,x));
    else v[x].push_back(make_pair(c,y));
    m--;
  }
}

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;
}

void solve(){
  for(int i=1; i<=n; i++){
    rang[i]=1;
    arb[i]=i;
  }
    pair<int,int> x;
    for(int i=2; i<=n; i++){
      sort(v[i].begin(), v[i].end());
      for(vector <pair<int,int> >::iterator it=v[i].begin(); it!=v[i].end(); it++){
        x=*it;
        if(find(i)!=find(x.second)){
          unite(i,x.second);
          s.push_back(make_pair(i,x.second));
          cost+=x.first;
          break;
        }
      }
    }
    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();
}