#include<iostream>
#include<queue>
#include<fstream>
#include<vector>
#define NMAX 200001
#define MMAX 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,c[NMAX];
struct muchie{int x,y,c;};
muchie ed[MMAX];
class cmpvf
{
public:
    bool operator () (const muchie&a,const muchie &b)

    {
        return a.c>b.c;
    }
};

priority_queue<muchie,vector<muchie>,cmpvf > h;
void read()
{
    fin>>n>>m;
  for(int i=1;i<=n;i++)c[i]=i;
    for(int i=1;i<=m;i++)
    {

      fin>>ed[i].x>>ed[i].y>>ed[i].c;
      //cout<<ed[i].c<<" ";
      h.push(ed[i]);
    }
    fin.close();

}
int main()
{
   read();
int nrmsel=0;
    muchie now;
    int cp, val=0;
    vector<muchie>sol;
  while(nrmsel<n&&!h.empty())
  {
      now=h.top();h.pop();
      if(c[now.x]!=c[now.y])
      {
          nrmsel++; val+=now.c;
          sol.push_back(now);
          if(c[now.x]<c[now.y])
          {   cp=c[now.y];
              for(int i=1;i<=n;i++)
              if(c[i]==cp)c[i]=c[now.x];
         }
         else
         {   cp=c[now.x];
             for(int i=1;i<=n;i++)
                if(cp==c[i])c[i]=c[now.y];
         }
  }
}
fout<<val<<'\n';
fout<<sol.size()<<'\n';

for(int i=0;i<sol.size();++i)
{
    fout<<sol[i].x<<" "<<sol[i].y<<'\n';
}
fout.close();
return 0;
}