#include <iostream>
#include <fstream>
using namespace std;
int a[100][100],tata[10000],oo=100000,n,m;
bool viz[10000];

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

void Prim(int nod_start)
{
    int i,p,minim,k,s=0;
    viz[nod_start]=1; //marcam nodul de start vizitat
    for(i=1;i<=n;i++)
        tata[i]=nod_start;
    tata[nod_start]=0;// initializam vectorul de tati
    for(k=1;k<=n-1;k++)
    {
        minim=oo; //minimul este initializat cu infinit
        p=0;
        for(i=1;i<=n;i++)
            if(!viz[i] && a[i][tata[i]]<minim) //cautam un nod nevizitat si il comparam cu minimul
            {
                minim=a[i][tata[i]];
                p=i;//retinem nodul in variabila p
            }
        if(minim!=oo)
            s+=minim;
        viz[p]=1; //il marcam vizitat la sfarsit
        for(i=1;i<=n;i++)
            if(!viz[i]&&a[i][tata[i]]>a[i][p])
                tata[i]=p;
    }
    fout<<s<<endl;
    fout<<n-1<<endl;
    for(int i=1;i<=n;i++)
        if(tata[i]!=0)
            fout<<i<<" "<<tata[i]<<endl;
}

int main()
{
    int i,j,C;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                a[i][j]=a[j][i]=oo;
    while(fin>>i>>j>>C)
        a[i][j]=a[j][i]=C;
    //cout<<"Nod de start = ";
    //cin>>x;
    Prim(3);
    return 0;
}