#include<stdio.h>
#include<algorithm>
#include <vector>
#define max 400100
using namespace std;

int X[max],Y[max],C[max],Gr[max],Ord[max];
vector<int> sol;
int costmin,n,m;

int grupa(int i)
{
     if (Gr[i]==i)
     return i;
     Gr[i]=grupa(Gr[i]);
     return Gr[i];
}

void reunire(int i,int j)
{
     Gr[grupa(i)]=grupa(j);
}
bool comparare(int i,int j)
{
    return (C[i]<C[j]);
}


int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
      {
           scanf("%d%d%d",&X[i],&Y[i],&C[i]);
           Ord[i]=i;
      }
    for (int i=1;i<=n;i++)
      Gr[i]=i;

    sort(Ord+1,Ord+m+1,comparare);

    for(int i=1;i<=m;i++)
        {
            if (grupa(X[Ord[i]])!=grupa(Y[Ord[i]]))
               {  costmin=costmin+C[Ord[i]];
                  reunire(X[Ord[i]],Y[Ord[i]]);
                  sol.push_back(Ord[i]);
               }
        }
 printf("%d\n",costmin);
 printf("%d\n",n-1);
 for(int i=0;i<n-1;++i)
        printf("%d %d\n",X[sol[i]],Y[sol[i]]);
return 0;
}