#include <fstream>
#define MAX 805

using namespace std;

typedef struct
{
    int x, y, cost, k;
}Muchie;

Muchie v[MAX], aux;

int a[MAX], n, m, nr, ok, X, Y, auxiliar;

void citire()
{
    int i;
    ifstream f("apm.in");

    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
}

void sortare()
{
    int i, j;
    for(i=1;i<=m;i++)
        for(j=i;j>1;j--)
            if(v[j-1].cost>v[j].cost)
                aux=v[j],v[j]=v[j-1],v[j-1]=aux;
}

void kruskal()
{
    int i;
    nr=0;
    ok=1;
    while(ok==1)
    {
        nr++;
        X=v[nr].x;
        Y=v[nr].y;
        if(a[X]+a[Y]==0)
        {
            a[X]=a[Y]=X;
            v[nr].k=1;
        }
        else
            if(a[X]*a[Y]==0)
            {
                a[X]=a[Y]=a[X]+a[Y];
                v[nr].k=1;
            }
            else
				if(a[X]!=a[Y])
					for(auxiliar=a[Y],v[nr].k=1,i=1;i<=n;i++)
						if(a[i]==auxiliar)
							a[i]=a[X];

        for(ok=0,i=1;i<=n;i++) if(a[i]==0) ok=1;
    }
}

void afis()
{
    ofstream g("apm.out");

    int i, s=0;
    for(i=1;i<=m;i++)
        if(v[i].k==1)
            s+=v[i].cost;

    g<<s<<endl<<n-1<<endl;

    for(i=1;i<=m;i++)
        if(v[i].k==1)
            g<<v[i].x<<" "<<v[i].y<<endl;
}

int main()
{
    citire();
    sortare();
    kruskal();
    afis();
    return 0;
}