#include <bits/stdc++.h>
#define NMAX 200009
#define MMAX 400009
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int tata[NMAX];
int h[NMAX];
int comp(int a);
void unire(int a, int b);
int n,m;
int cmin;
void citire();
struct muchie {int x; int y;int c;};
bool operator <(muchie a, muchie b)
{
  return a.c>b.c;
}
priority_queue<muchie> H ;
vector<muchie>sol;
void krusk();
int main()
{citire();
 krusk();
 fout<<cmin<<'\n'<<sol.size()<<'\n';

 for(int i=0;i<sol.size();i++)
      fout<<sol[i].x<<" "<<sol[i].y<<'\n';
 return 0;
}
void citire()
{int i;
 int x,y,c;
  fin>>n>>m;
  for(i=1;i<=m;i++)
    {
     fin>>x>>y>>c;
     H.push({x,y,c});
    }
}
void krusk()
{int i=1;
 int nrsel=0;
 while(!H.empty() && nrsel!=n-1)
    {
     muchie act;
     act=H.top();H.pop();
     int xx=act.x;
     int yy=act.y;
     int c=act.c;
     int cx=comp(xx);
     int cy= comp(yy);
     if(cx!=cy)
        {unire(cx,cy);nrsel++;cmin+=c;sol.push_back(act);}

    }
}
int comp(int tr)
{
 int cop;
 int rez;
 int act;
 rez=tr;
 while(tata[rez])
      rez=tata[rez];
 cop=tr;
 while(tata[cop])
        {act=cop;
         cop=tata[cop];
         tata[act]=rez;
        }
 return rez;
}
void unire(int x, int y)
{
 if(h[x]>h[y])
    tata[y]=x;
  else
   if(h[x]<h[y])
      tata[x]=y;
 else
 {
  h[x]++;tata[y]=x;
 }
}