#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
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;

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

struct cmp {

  bool operator () (const int &a,const int &b) {

    return Dst[a]>Dst[b];
  }
}; priority_queue <int,vector <int>,cmp> Q;

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 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 (!inQueue[it->first]) {

        inQueue[it->first]=1;
        Q.push (it->first);
      }
    }
}

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

  memset (Dst,INF,sizeof (Dst));

  Q.push (1); Dst[1]=0;
  for (i=1; i<=N; ++i) {

    nod=Q.top (); Q.pop ();
    inQueue[nod]=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;
}