#include <fstream>
#include <algorithm>
#define nmax 200001
#define nmax2 400001
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, t[nmax], r1, r2,cost, ok[nmax2], nr;

struct muchie
{
    int a, b, c;
};

muchie v[nmax];

bool cmp(const muchie &a,const muchie &b)
{
    return a.c<b.c;
}

int rad(int x)
{
    while(t[x]>0)
     x=t[x];
  return x;
}

int main()
{ int i;
    f>>n>>m;
    for(i=1; i<=m; i++)
        f>>v[i].a>>v[i].b>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=n; i++)
        t[i]=-1;
    for(i=1;i<=m;i++){
        r1=rad(v[i].a);
        r2=rad(v[i].b);
         if(r1!=r2){
            cost+=v[i].c;
            nr++;
            ok[i]=1;
            if(nr==n-1)
                break;

            if (t[r1]<t[r2]) {
                t[r1]+=t[r2];
                t[r2]=r1;
            }
            else {
                t[r2]+=t[r1];
                t[r1]=r2;
            }
         }
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=m;i++)
       if(ok[i]==1)
         g<<v[i].b<<' '<<v[i].a<<'\n';

    return 0;
}