#include <bits/stdc++.h>

using namespace std;

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

int n,m,cost;
struct muchie{

  int cost,s,d;

} a[400010];
int L[200001],R[200001];
int b[200001],nrelem;

bool comp(muchie i, muchie j)
{
    return (i.cost<j.cost);
}

int rad(int x){
    while(L[x])
        x = L[x];
    return x;
}

int main()
{
 f>>n>>m;

 for(int i=1;i<=m;++i)
    R[i]=1;

 for(int i=1;i<=m;++i)
    f>>a[i].s>>a[i].d>>a[i].cost;

 sort(a+1,a+1+m,comp);

 for(int i=1;i<=m && nrelem<n-1 ;++i)
 {
     int Rx=rad(a[i].s);
     int Ry=rad(a[i].d);
   if(Ry!=Rx)
   {
       b[++nrelem]=i;
       cost+=a[i].cost;

       if(R[Rx]>R[Ry])
       {
           R[Rx] += R[Ry];
                L[Ry] = Rx;
       }
       else
       {
           R[Ry] += R[Rx];
                L[Ry] = Ry;
       }
   }

 }
   g<<cost<<'\n'<<n-1<<'\n';
   for(int i=1;i<=n-1;++i)
    g<<a[b[i]].d<<" "<<a[b[i]].s<<'\n';

return 0;
}