#include <fstream>
#define v 400004
#define vv 200004

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct nod
{
   int n1,n2;
   nod *next;
};

nod *nd, *ul;
int x[v],y[v],c[v],e[vv],rang[vv],n,m;

void citire()
{
    fin >> n >> m;
    for (int i=0; i<m; i++)
    {
        fin >> x[i] >> y[i] >> c[i];
        if (i<=n)
            e[i]=i,rang[i]=1;
    }
}

int cauta(int p)
{
	int R, o;
	for (R=p; e[R]!=R; R=e[R]);
	for (; e[p]!=p; )
	{
		o=e[p];
		e[p]=R;
		p=o;
	}
	return R;
}

void unite(int x, int y)
{
	if (rang[x]>rang[y])
		e[y]=x;
    else e[x]=y;
	if (rang[x]==rang[y])
        rang[y]++;
}

void sortare(int l, int r)
{
    int i,j,u,z;
    i=l;
    j=r;
    u=c[(l+r)/2];
    //do
    while (i<=j)
    {
        while (c[i]<u)
            ++i;
        while (u<c[j])
            --j;
        if (i<=j)
        {
            z=c[i];
            c[i]=c[j];
            c[j]=z;
            z=x[i];
            x[i]=x[j];
            x[j]=z;
            z=y[i];
            y[i]=y[j];
            y[j]=z;
            ++i;
            --j;
        }
    }
//    while (i<=j);
    if (l<j)
        sortare(l,j);
    if (i<r)
        sortare(i,r);
}

void add(int x, int y)
{
    nod *f;
    f=new nod;
    f->n1=x;
    f->n2=y;
    f->next=NULL;
    if (nd==NULL)
        nd=ul=f;
    else
    {
        ul->next=f;
        ul=f;
    }
}

int main()
{
    citire();
    nd=new nod;
    nd=NULL;
    sortare(0,m-1);
    int X,Y,cost=0;
    for (int i=0; i<m; i++)
    {
        X=cauta(x[i]);
        Y=cauta(y[i]);
        if (X!=Y)
        {
            cost+=c[i];
            add(x[i],y[i]);
            unite(X,Y);
        }
    }
    //printf("%d\n%d\n",cost,n-1);
    fout << cost << "\n" << n-1 << "\n";
    for (nod *p=nd; p; p=p->next)
        //printf("%d %d\n",p->n1,p->n2);
        fout << p->n1 << " " << p->n2 << "\n";
    return 0;
}