#include<stdio.h>
#include<vector>
using namespace std;

const int maxn=200005,inf=99999999;
int n,m,nh,cost;
int x[maxn],d[maxn],poz[maxn],t[maxn];
struct nod{int inf,c;nod *urm;};
nod *l[maxn];

void add(int a,int b,int c)
{
	nod *q;

	q->inf=b;
	q->c=c;
	q->urm=l[a];
	l[a]=q;
}

void cit()
{
    int i;
    int a,b,c;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
		add(b,a,c);

    }

	for(i=1;i<=n;i++)
	{
		x[i]=i;
		poz[i]=i;
		d[i]=inf;
		t[i]=1;
	}
    nh=n;
    d[1]=0;
}

void swap(int i,int j)
{
    int aux;
    aux=x[i];
    x[i]=x[j];
    x[j]=aux;
    poz[x[i]]=i;
    poz[x[j]]=j;
}

void heap_up(int k)
{
    int i;
    if(k<=1) return;

    i=k/2;
    if(d[x[i]]>d[x[k]])
    {
        swap(i,k);
        heap_up(i);
    }
}

void heap_dw(int k)
{
    int i=2*k;

    if(i<=nh)
    {
        if(i+1<=nh && d[x[i+1]]<d[x[i]]) i++;

        if(d[x[i]]<d[x[k]])
        {
            swap(i,k);
            heap_dw(i);
        }
    }
}

int min_heap()
{
    swap(1,nh);
    poz[x[nh]]=0;
    nh--;

    return x[nh+1];
}

void prim()
{
	nod *q;
    int k;

    while(nh>0)
    {
        k=min_heap();
        heap_dw(1);

        cost+=d[k];

		q=l[k];
		while(q)
		{
            if(poz[q->inf] && q->c<d[q->inf])
            {
                d[q->inf]=q->c;
                t[q->inf]=k;
                heap_up(poz[q->inf]);
            }
            q=q->urm;
		}
    }
}

void afis()
{
    int i;

    printf("%d\n%d\n",cost,n-1);
    for(i=2;i<=n;i++)
        printf("%d %d\n",i,t[i]);

}

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

    cit();
    prim();
    afis();

    fclose(stdin);
    fclose(stdout);
    return 0;
}