#include <fstream>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,cost;};
int n,m;
muchie muc[400001];
int d[400001],T[200001],G[200001];
int cauta(int x){int R,aux;
                 for(R=x;T[R]!=R;R=T[R])
                        while(x!=R){aux=T[x];
                                    T[x]=R;
                                    x=aux;
                                    }
                    return R;
                }
void uneste(int x,int y){if(G[x]>G[y])T[y]=x;
                             else T[x]=y;
                         if(G[x]==G[y])G[y]++;
                         }

bool cmp(int a,int b){return muc[a].cost<muc[b].cost;}
int main()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        {fin>>muc[i].x;
         fin>>muc[i].y;
         fin>>muc[i].cost;
        }
    for(i=1;i<=n;i++){T[i]=i;G[i]=1;}

    for(i=1;i<=m;i++)d[i]=i;
    sort(d+1,d+m+1,cmp);
    int c=0,nrm=0;
    int care[200000];
    for(i=1;i<=m;i++)
        {int a,b;
          a=cauta(muc[d[i]].x);b=cauta(muc[d[i]].y);
          if(a!=b){uneste(a,b);
                   c+=muc[d[i]].cost;
                   care[++nrm]=d[i];}
        }
    fout<<c<<"\n";
    fout<<nrm<<"\n";
    for(i=1;i<=nrm;i++)
        fout<<muc[care[i]].x<<" "<<muc[care[i]].y<<"\n";
      return 0;
}