#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream d("apm.in");
ofstream o("apm.out");
int n,m,i,j,k,ct,v[200002],x,y,c;
vector <pair<int,pair<int,int> > > a[200005];
vector <pair<int,pair<int,int> > >::iterator it;
vector <pair<int,int> > vs;
vector <pair<int,int> >::iterator itt;
pair<int,pair<int,int> > e;
priority_queue
<
  pair<int,pair<int,int> >,
  vector <pair<int,pair<int,int> > >,
  greater <pair<int,pair<int,int> > >
> q;
int main()
{
  d>>n>>m;
  for (i=1;i<=m;i++)
    {
      d>>x>>y>>c;
      a[x].push_back(make_pair(c,make_pair(x,y)));
      a[y].push_back(make_pair(c,make_pair(y,x)));
    };
  for (it=a[1].begin();it!=a[1].end();it++)
    {
      q.push(*it);
    };
  v[1]=1;
  while (k<n-1)
    {
      e=q.top();
      q.pop();
      if (v[e.second.second]==0)
        {
          v[e.second.second]=1;
          k++;
          vs.push_back(e.second);
          ct+=e.first;
          for (it=a[e.second.second].begin();it!=a[e.second.second].end();it++)
            {
              q.push(*it);
            };
        };
    };
  o<<ct<<'\n'<<k<<'\n';
  for (itt=vs.begin();itt!=vs.end();itt++) o<<(*itt).first<<' '<<(*itt).second<<'\n';
}