#include<fstream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
typedef long long int ll;
int n,m,i,j,a,b,c;
 vector<pair<pair<int,int>,int>>v;
 vector<pair<int,int>>apm;
int par[200001],rnk[200001];
ll cost;
bool comp(const pair<pair<int,int>,int>&x, const pair<pair<int,int>,int>&y)
{
  return x.second<y.second;
}
int caut(int x)
{
  if(par[x]==x)
    return x;
  else
  {
    par[x]=caut(par[x]);
    return par[x];
  }
}
int main()
{
  ios::sync_with_stdio(false);
  fin.tie(0);
  fin>>n>>m;
  for(i=1;i<=m;++i)
  {
    fin>>a>>b>>c;
    v.push_back({{a,b},c});
  }
  for(i=1;i<=n;++i)
  {
    par[i]=i;
    rnk[i]=1;
  }
  sort(v.begin(),v.end(),comp);
  for(i=0;i<=m-1;++i)
  {
    int u=caut(v[i].first.first);
    int x=caut(v[i].first.second);
    if(u==x) continue;
    if(rnk[u]==rnk[x])
    {
      rnk[u]++;
    }
    else if(rnk[u]<rnk[x])
    {
      swap(u,x);
    }
    par[x]=u;
    cost+=v[i].second;
    apm.push_back({v[i].first.first,v[i].first.second});
  }
  fout<<cost<<'\n';
  fout<<apm.size()<<'\n';
  for(auto y: apm)
    fout<<y.first<<" "<<y.second<<'\n';
  return 0;
}