#include <iostream>
#include <fstream>
#define Nnoduri 200005
#define Nmuchii 400005

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie
{
    int e1,e2,cost;
};

Muchie G[Nmuchii];
int A[Nnoduri],c[Nnoduri];
int n,m;
int sum;

void citire()
{
    fin>>n>>m;

    for(int i=1;i<=m;++i)
        fin>>G[i].e1>>G[i].e2>>G[i].cost;

    for(int i=1;i<=n;++i)c[i]=i;
    fin.close();
}

void afisare(int NrMSel)
{  fout<<sum<<"\n";
fout<<NrMSel<<"\n";
    for(int i=1;i<n;++i)
        fout<<G[A[i]].e1<<" "<<G[A[i]].e2<<"\n";
    fout.close();
}

void sortareMuchii(int st ,int dr)
{
    int i,j;

    Muchie x;

    if(st<dr)
    {
        x=G[st];
        i=st;
        j=dr;
          while(i<j)
          {
              while(i<j && G[j].cost>=x.cost)j--;
              G[i]=G[j];
              while(i<j && G[i].cost<=x.cost)i++;
              G[j]=G[i];
          }

          G[i]=x;
          sortareMuchii(st,i-1);
          sortareMuchii(i+1,dr);
    }
}


int main()
{
    int minim,maxim;
    int NrMSel=0;

    citire();

    sortareMuchii(1,m);

    for(int i=1;NrMSel<n-1;++i)
        if(c[G[i].e1]!=c[G[i].e2])
    {
        A[++NrMSel]=i;
        sum+=G[i].cost;

        if(c[G[i].e1]<c[G[i].e2])
        {
            minim=c[G[i].e1];
            maxim=c[G[i].e2];
        }
        else{
            minim=c[G[i].e2];
            maxim=c[G[i].e1];
        }

        for(int j=1;j<=n;++j)
            if(c[j]==maxim)c[j]=minim;
    }
    afisare(NrMSel);
    return 0;
}