#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,gr[200067],cost;
      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();
      }
      void init()
      {
           for(int i=0;i<=n;++i)gr[i]=i;
      }
      void sorT()
      {
           sort(a,a+m,cmp);
      }
      void uneste(int x,int y)
      {
           int i,j;
           i=gr[x];
           j=gr[y];
           for(int k=1;k<=n;++k)
           if(gr[k]==i)gr[k]=j;
      }
      void APM()
      {
           int i,j;
           for(i=0;i<m;++i)
           {
                           if(gr[a[i].x]==gr[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;
}