#include<stdio.h>
#include<vector>
#define maxn 200005
#define MAXX 999999999

using namespace std;

int n,m,d[maxn],poz[maxn],x[maxn],nh,r,t[maxn],cost;

vector <int > v[maxn],vc[maxn];


void cit()
{
	int i,p1,p2,cc;

	scanf("%d %d",&n,&m);

     r=1;

	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&p1,&p2,&cc);

		v[p1].push_back(p2);
		vc[p1].push_back(cc);
		v[p2].push_back(p1);
		vc[p2].push_back(cc);
	}
}




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 heapup(int k)
{
	int i;

	if(k<=1)
		return ;

	i=k/2;

	if(d[x[k]]<d[x[i]])
	{
		swap(i,k);
		heapup(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 scoate_heap()
{
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;

	return x[nh+1];
}




void prim()
{
	int p,nrq;
	unsigned int i;

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


	d[r]=0;
	nh=n;


	while(nh>0)
	{
		p=scoate_heap();
		heap_dw(1);

       cost+=d[p];
       nrq=v[p].size();

		for(i=0;i<nrq;i++)
		{
			if(d[v[p][i]]>vc[p][i] && poz[v[p][i]])
			{
				d[v[p][i]]=vc[p][i];
                t[v[p][i]]=p;

				heapup(poz[v[p][i]]);
			}
		}
	}
}





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