#include <fstream>
#include<algorithm>
#define NMAX 400001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
struct elem
{
    int x,y,cost;
}v[NMAX],sol[NMAX];
int n,m,k,costt,tata[200001];
bool cmp(elem x,elem y)
{
    return x.cost<y.cost;
}
int radacina(int x)
{
    if(x==tata[x])
        return x;
    else
        return tata[x]=radacina(tata[x]);
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++)
        tata[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=v[i].x;
        int y=v[i].y;
        int cost=v[i].cost;
        int radx=radacina(x);
        int rady=radacina(y);
      if(radx!=rady)
      {
           costt+=cost;
           tata[rady]=radx;
           sol[++k].x=x;
           sol[k].y=y;
      }
    }
    fout<<costt<<"\n";
    fout<<k<<"\n";
    for(int i=1;i<=k;i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}