#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {int A,B,C;};
muchie a[400001];
int n,m,t[200001],niv[200001],mukie[200001];

inline bool cp(muchie m1,muchie m2)
{ if(m1.C<m2.C) return 1;
    return 0;
}
int Find(int x)
{ while(t[x]!=0) x=t[x];
   return x;

}
void Union(int x,int y)
{if(niv[x]>niv[y]) t[y]=x;
  else { t[x]=y;
    if(niv[x]==niv[y]) niv[y]++;
  }

}

int main()
{  int i,mu=0,ct=0,x,y,s=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>a[i].A>>a[i].B>>a[i].C;
    sort(a+1,a+m+1,cp);
    i=1;
    while(mu<n-1)
    {
        x=Find(a[i].A);
        y=Find(a[i].B);
        if(x!=y)
        {mu++;
            mukie[++ct]=a[i].B;
            mukie[++ct]=a[i].A;
            Union(x,y);
            s=s+a[i].C;
        }
        i++;
    }
    fout<<s<<"\n"<<n-1<<"\n";
    for(i=1;i<=ct;i=i+2)
        fout<<mukie[i]<<" "<<mukie[i+1]<<"\n";
    return 0;
}