#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,t[200067],cost,rang[200067];
      struct G{int x,y,c;};
      G a[400067];
      vector <G> s;
bool cmp(G t,G q)
      {
           return t.c<q.c;
      }
namespace solve
{
      void read()
      {
           fstream in;
           in.open("apm.in",ios::in);
           in>>n>>m;
           for(int i=0;i<m;++i)
           in>>a[i].x>>a[i].y>>a[i].c;
           in.close();
      }
      int multime(int r)
      {
           if(t[r]!=r)
           t[r]=multime(t[r]);
           return t[r];
      }
      void init()
      {
           for(int i=0;i<=n;++i)t[i]=i,rang[i]=0;
      }
      void sorT()
      {
           sort(a,a+m,cmp);
      }
      void uneste(int i,int j)
      {
          i=multime(i);
          j=multime(j);
          if(i==j)return;
          if(rang[i]<rang[j])
          t[i]=j;
          else t[j]=i;
          if(rang[i]==rang[j])rang[i]++;
      }
      void APM()
      {
           int i,j;
           for(i=0;i<m;++i)
           {
                           if(multime(a[i].x)==multime(a[i].y))continue;
                           uneste(a[i].x,a[i].y);
                           cost+=a[i].c;
                           s.push_back(a[i]);
           }
      }
      void write()
      {
           fstream out("apm.out",ios::out);
           out<<cost<<'\n';
           out<<s.size()<<'\n';
           for(int i=0;i<s.size();++i)
           out<<s[i].y<<' '<<s[i].x<<'\n';
           out.close();
      }
};
int main()
{
    solve::read();
    solve::init();
    solve::sorT();
    solve::APM();
    solve::write();
    return 0;
}