#include <fstream>
#define dmax 200005

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

struct muchie
{
    int x,y,cost;
};
muchie u[dmax],arb[dmax];
int n,m,costAPM,sel[dmax],nrm;

void citire()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>u[i].x>>u[i].y>>u[i].cost;
}

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

void PRIM()
{
    int i,j,x,y,cost;
    x=u[1].x;y=u[1].y;cost=u[1].cost;arb[1].cost=cost;
    sel[x]=sel[y]=1;costAPM=costAPM+cost;
    arb[1].x=x;arb[1].y=y;
    //fout<<"Am selectat: "<<x<<" "<<y<<" "<<cost<<'\n';
    //fout<<sel[x]<<" "<<sel[y]<<'\n';
    nrm=1;
    while(nrm<n-1)
        for(i=2;i<=m;i++)
            {
                x=u[i].x;y=u[i].y;cost=u[i].cost;
                if(sel[x]!=sel[y])
                   {
                   //    fout<<"Am selectat: "<<x<<" "<<y<<" "<<cost<<'\n';
                       nrm=nrm+1;
                       sel[x]=sel[y]=1;costAPM+=cost;
                       arb[nrm].x=x;arb[nrm].y=y;arb[nrm].cost=cost;
                       //fout<<sel[x]<<" "<<sel[y]<<'\n';
                       break;
                   }
            }
}

int main()
{
    int i;
    citire();
    sortare();
    /*fout<<"Muchii sortate dupa cost\n";
    for(i=1;i<=m;i++)
        fout<<u[i].x<<" "<<u[i].y<<" "<<u[i].cost<<'\n';
    fout<<"Ordinea de selectare a muchiilor prin algoritmul lui PRIM\n";*/
    PRIM();
    fout<<costAPM<<'\n';
    //fout<<"Muchiile arborelui\n";
    fout<<nrm<<'\n';
    for(i=1;i<=nrm;i++)
        fout<<arb[i].x<<" "<<arb[i].y<<'\n';
    return 0;
}