#include <fstream>
#include <vector>
#include <algorithm>

#define NMAX 200000

using namespace std;

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

struct Muchie
{
    int x;
    int y;
    int cost;
};

void citire();
int compara(Muchie a,Muchie b);
void afisare();
void kruscal();

Muchie graf[NMAX];

int APM[NMAX],conex[NMAX];

int n,m,cost_apm,nrm;

int main()
{
    citire();
    sort(graf+1,graf+m+1,compara);
    kruscal();
    /*for(int i=1;i<=m;i++)
    {
        fout<<graf[i].x<<' ';
        fout<<graf[i].y<<' ';
        fout<<graf[i].cost<<' ';
        fout<<'\n';
    }*/
    afisare();
    return 0;
}

void kruscal()
{
    int i,j,minim,maxim;
    for(i=1;i<=n-1;i++)
    {
        if(conex[graf[i].x]!=conex[graf[i].y])
        {
            APM[++nrm]=i;//retin muchia
            cost_apm+=graf[i].cost;
            if(conex[graf[i].x]!=conex[graf[i].y])
            {
                minim=conex[graf[i].y];
                maxim=conex[graf[i].x];
            }
            else
            {
                minim=conex[graf[i].x];
                maxim=conex[graf[i].y];
            }
            for(j=1;j<=n;j++)
                if(conex[j]==maxim)
                        conex[j]=minim;
        }

    }
}

void afisare()
{
    int i;
    fout<<cost_apm<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        fout<<graf[APM[i]].x<<' '<<graf[APM[i]].y<<'\n';
}

int compara(Muchie a,Muchie b)
{
    return a.cost<b.cost;
}

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