#include <cstdio>
#include <vector>

using namespace std;

struct ceva{
short int nod,c;
};
bool sol[200005],viz[200005];
short int h[200005],nod[200005],cost[200005],sol2[200005][2],init[200005],size_heap=0,size_sol=0,n,m; //nod e vector de pozitie
long long sum;
vector <ceva> v[200005];

void swap(int a,int b)
{
    int tmp=h[b];
    h[b]=h[a];
    h[a]=tmp;
    tmp=nod[h[b]];
    nod[h[b]]=nod[h[a]];
    nod[h[a]]=tmp;
}

void up(int poz)
{
   while(poz!=1)
   {
       if(cost[h[poz]] < cost[h[poz/2]])
       {
           swap(poz,poz/2);
       }
       else
           break;
       poz/=2;
   }
}

void down(int poz)
{
     int dest=poz;

     if(2*poz<=size_heap && cost[h[2*poz]] < cost[h[dest]])//dest=poz
         dest=2*poz;
     if(2*poz+1<=size_heap && cost[h[2*poz+1]] < cost[h[dest]])//dest=(poz?2*poz)
          dest=2*poz+1;

     if(dest!=poz)
      {
          swap(dest,poz);
          down(dest);
      }
}

void adauga(ceva x,int k)
{
    if(sol[x.nod]==0) //aici verific in loc de vector de viz
    if(viz[x.nod]==0)
    {
     viz[x.nod]=1;
     init[x.nod]=k;
     h[++size_heap]=x.nod;
     nod[x.nod]=size_heap;
     cost[x.nod]=x.c;
     up(size_heap);
    }
    else
    {
     if(x.c<cost[x.nod]){
        cost[x.nod]=x.c;
        init[x.nod]=k;
        up(nod[x.nod]);
     }
    }
}

void elim(int poz)
{
     swap(poz, size_heap);
     size_heap--;
     up(poz);
     down(poz);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    short int tmp1,tmp2,tmp3,cn;

    scanf("%hd %hd",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%hd %hd %hd",&tmp1,&tmp2,&tmp3);
        v[tmp1].push_back({tmp2,tmp3});
        v[tmp2].push_back({tmp1,tmp3});
    }

    for(int i=0;i<v[1].size();++i)
        adauga(v[1][i],1);

    sol[1]=1;
    cn=n;
    --n;
    while(n)
    {
        sol[h[1]]=1;
        sum+=cost[h[1]];
        sol2[++size_sol][0]=init[h[1]];
        sol2[size_sol][1]=h[1];
        tmp1=h[1];
        tmp2=cost[h[1]];
        elim(1);
        for(int i=0;i<v[tmp1].size();++i)
        {
            //v[tmp1][i].c+=tmp2;
            //if(sol[v[tmp1][i].nod]==0)
                adauga(v[tmp1][i],tmp1);
        }
        --n;
    }

    printf("%lld\n%hd\n",sum,size_sol);
    for(int i=1;i<=size_sol;++i)
        printf("%hd %hd\n",sol2[i][0],sol2[i][1]);

    return 0;
}