#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

int *p,cost,*cheie,*h,*poz,n,m,l;
vector <pair<int,int> > Q[200200],A;

void introduce_in_apm(int x)
{
    for(int i=0;i<Q[x].size();++i)
    {
        int nod = Q[x][i].first;
        int cost = Q[x][i].second;
        cheie[nod] = min(cheie[nod],cost);
        if (cheie[nod] == cost)
            p[nod] = x;
    }
}

void push(int po)
{
    while((po*2<=l && cheie[h[po]] > cheie[h[po*2]]) || (po*2+1<=l && cheie[h[po]] > cheie[h[po*2+1]]))
    {
        if (cheie[h[po*2]] < cheie[h[po*2+1]] || po*2+1>l)
        {
            swap(h[po],h[po*2]);
            swap(poz[h[po]],poz[h[po*2]]);
            po*=2;
        }
        else
        {
            swap(h[po],h[po*2+1]);
            swap(poz[h[po]],poz[h[po*2+1]]);
            po=po*2+1;
        }
    }
}


void pop(int po)
{
    while(po > 1 && cheie[h[po]] < cheie[h[po/2]])
    {
        swap(h[po],h[po/2]);
        swap(poz[h[po]],poz[h[po/2]]);
        po=po/2;
    }
}

int scoate_radacina_h()
{
    int x = h[1];
    swap(h[1],h[l]);
    swap(poz[h[1]],poz[h[l]]);
    l--;
    push(1);
    poz[x] = 0;
    return x;
}

void citire()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        Q[x].push_back(make_pair(y,c));
        Q[y].push_back(make_pair(x,c));
    }

    cheie=new int[200200];
    for(int i=1;i<=n;++i)
        cheie[i] = 200000200;
    cheie[1] = 0;
}

int main()
{

    citire();
    p=new int[200200];

    introduce_in_apm(1);

    poz=new int[200200];
    h=new int[2*200200+100];

    for(int i=2;i<=n;++i)
      {
          h[++l] = i;
          poz[i] = l;
          pop(l);
      }


    for(int i=1;i<n;++i)
    {
        int x = scoate_radacina_h();
        introduce_in_apm(x);
        cost+=cheie[x];
        A.push_back(make_pair(x,p[x]));
        for(int j=0;j<Q[x].size();++j)
        {
            int nod = Q[x][j].first;
            if (poz[nod])
                pop(poz[nod]);
        }
    }
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(unsigned int i=0;i<n-1;++i)
        printf("%d %d\n",A[i].first,A[i].second);
    return 0;
}