#include <cstdio>
#include <vector>
#define t(x)    ((x)/2)
#define fs(x)   ((x)*2)
#define fd(x)   ((x)*2+1)
#define MaxN 200009
#define MaxM 400009
#define MaxC 1009

using namespace std;

struct muchie {int a,b,c;} heap[MaxN];

vector <int> v[MaxN],cs[MaxN],x,y,nod;
int n,m,C,uz[MaxN],N;

void cit()
{
    int i,x,y,c;
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(y); cs[x].push_back(c);
        v[y].push_back(x); cs[y].push_back(c);
    }
}

void swap(int x,int y)
{
    muchie aux;
    aux=heap[x]; heap[x]=heap[y]; heap[y]=aux;
}

void urca(int nod)
{
    while(nod>1 && heap[t(nod)].c>heap[nod].c)
        swap(t(nod),nod), nod=t(nod);
}

void add(int x,int y,int cost)
{
    N++;
    heap[N].a=x; heap[N].b=y; heap[N].c=cost;
    urca(N);
}

void coboara(int nod)
{
    while((fs(nod)<=N && heap[fs(nod)].c<heap[nod].c) || (fd(nod)<=N && heap[fd(nod)].c<heap[nod].c))
        if(fd(nod)<=N)
        {
            if(heap[fs(nod)].c<heap[fd(nod)].c)
                swap(fs(nod),nod), nod=fs(nod);
            else
                swap(fd(nod),nod), nod=fd(nod);
        }
        else
            swap(fs(nod),nod), nod=fs(nod);
}

void sol()
{
    int nr,xi,yi,s,i;
    uz[1]=1; nod.push_back(1);
    for(i=0;i<v[1].size();i++)
        add(1,v[1][i],cs[1][i]);
    nr=1;
    while(nr<n)
    {
        xi=heap[1].a; yi=heap[1].b; s=heap[1].c;
        while(uz[yi])
        {
            heap[1]=heap[N]; heap[N].a=0; heap[N].b=0; heap[N].c=0; N--;
            coboara(1);
            xi=heap[1].a; yi=heap[1].b; s=heap[1].c;
        }
        x.push_back(xi); y.push_back(yi);
        C+=s;
        heap[1]=heap[N]; heap[N].a=0; heap[N].b=0; heap[N].c=0; N--;
        coboara(1);
        uz[yi]=1;
        for(i=0;i<v[yi].size();i++)
            if(!uz[v[yi][i]])
                add(yi,v[yi][i],cs[yi][i]);
        nr++;
    }
}



void afis()
{
    int i;
    freopen("apm.out","w",stdout);
    printf("%d\n",C);
    printf("%d\n",n-1);
    for(i=0;i<x.size();i++)
        printf("%d %d\n",x[i],y[i]);
}

int main()
{
    cit();
    sol();
    afis();
    return 0;
}