#include<fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,i,j,k;
struct muchie
{
    int x1,x2,cost,k;}u[20],aux;

int L[20];    //L-lista varf. graf.
int p;        //p-camp de lucru
int v,w;    //v,w-pastreaza extremitatile muchiilor
int ct;        //ct-camp de lucru; insumeaza costurile

int main()
{
    
    in>>n>>m;
    
    for (i=1;i<=m;i++)
    {
        in>>u[i].x1>>u[i].x2>>u[i].cost;
        L[i]=i;
    }
    
    p=m;
    
    while (p>1)
    {
        k=0;
        for (i=1;i<p;i++)
            if (u[i].cost>u[i+1].cost)
            {
                aux=u[i];
                u[i]=u[i+1];
                u[i+1]=aux;
                k=i;
            }
        p=k;
    }
    
    k=0;
    i=1;
    
    while(k<n-1)
    {
        if (L[u[i].x1]!=L[u[i].x2])
        {
            k++;
            ct+=u[i].cost;
			u[i].k=1;
            v=L[u[i].x2];
            w=L[u[i].x1];
            for (j=1;j<=n;j++)
                if (L[j]==v)
                    L[j]=w;
        }
        i++;
    }
    
    out<<ct<<'\n'<<n-1<<'\n';
    
	for (i=1;i<=n;i++)
		if(u[i].k)
			out<<u[i].x1<<" "<<u[i].x2<<'\n';
    in.close();
    out.close();
    return 0;
}