#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

#define INF 0x3f3f3f3f
#define DIM 200005

vector <pair <int,int> > G[DIM];
vector <pair <int,int> > muchii;

int Dst[DIM],Tat[DIM];
int h[DIM],poz[DIM];
bool inTree[DIM];
int N,M,L,cost;

void read () {
  int i,x,y,z;

  fin>>N>>M;
  for (i=1; i<=M; ++i) {

    fin>>x>>y>>z;
    G[x].push_back (make_pair (y,z));
    G[y].push_back (make_pair (x,z));
  }
}

inline void upheap (int nod)
{
  int tata;

  for ( ; nod>1; ) {

    tata=nod>>1;
    if (Dst[h[tata]]>Dst[h[nod]]) {

      poz[h[tata]]=nod;
      poz[h[nod]]=tata;
      swap (h[tata],h[nod]);
      nod=tata;
    }
    else
        return ;
  }
}

inline void downheap (int nod) {
  int fiu;

  for ( ; nod<=L ;) {

    if ((nod<<1)<=L) {

      fiu=nod<<1;
      if (fiu+1<=L && Dst[h[fiu+1]]<Dst[h[fiu]])
        ++fiu;
    }
    else
        return ;
    if (Dst[h[nod]]>Dst[h[fiu]]) {

      poz[h[fiu]]=nod;
      poz[h[nod]]=fiu;
      swap (h[fiu],h[nod]);
      nod=fiu;
    }
    else
        return ;
  }
}

inline void insert (int nod) {
  vector <pair <int,int> > :: iterator it;

  inTree[nod]=1;
  if (Tat[nod]) {

    muchii.push_back (make_pair (nod,Tat[nod]));
    cost+=Dst[nod];
  }

  for (it=G[nod].begin (); it!=G[nod].end (); ++it)
    if (!inTree[it->first] && it->second<Dst[it->first]) {

      Dst[it->first]=it->second;
      Tat[it->first]=nod;

      if (!poz[it->first])
        poz[h[++L]=it->first]=L;
      upheap (poz[it->first]);
    }
}

void solve () {
  vector <pair <int,int> > :: iterator it;
  int i,nod;

  memset (Dst,INF,sizeof (Dst));
  L=1;

  h[1]=poz[1]=1; Dst[1]=0;
  for (i=1; i<=N; ++i) {

    nod=h[1]; h[1]=h[L--]; poz[h[1]]=1; downheap (1);
    insert (nod);
  }

  fout<<cost<<"\n"<<N-1<<"\n";
  for (it=muchii.begin (); it!=muchii.end (); ++it)
      fout<<it->first<<" "<<it->second<<"\n";
}

int main () {

  read ();
  solve ();

  return 0;
}