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

using namespace std;

const int maxn = 200200;
const int INF = 200000200;

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

void introduce_in_apm(int x)
{
    for(unsigned 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;
    }
}

void introduce_in_h(int nod)
{
    h[++l] = nod;
    poz[nod] = l;
    pop(l);
}

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[maxn];
    for(int i=1;i<=n;++i)
        cheie[i] = INF;
    cheie[1] = 0;
}

int main()
{

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

    introduce_in_apm(1);

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

    for(int i=2;i<=n;++i)
      introduce_in_h(i);


    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(unsigned 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;
}