#include <fstream>
#include <algorithm>
#define IN "apm.in"
#define OUT "apm.out"
#define MMAX 400005
#define NMAX 200005

using namespace std;

ifstream fin (IN);
ofstream fout (OUT);

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

Muchie G[MMAX];
int apm[NMAX], conex[NMAX];
int n,m, C_apm;

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

void afisare()
{
    int i;

    fout<<C_apm<<'\n';
    fout<<n-1<<'\n';

    for (int i=1; i<=n-1; i++)
        fout<<G[apm[i]].y<<" "<<G[apm[i]].x<<'\n';

}

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

    for (int i=1; i<=n; i++)
        conex[i]=i;
}


int main()
{
    citire();
    sort(G, G+m, compara);

    int min, max, poz=0;

    for (int i=1; i<=n-1; i++)
        for (int j=poz; j<m; j++)
            if (conex[G[j].x] != conex[G[j].y])//verific sa nu fie cicluri
            {
                C_apm+=G[j].cost;

                apm[i]=j;

                //unificam
                //Toate mai mari se duc in cele mici
                if (conex[G[j].x] < conex[G[j].y])
                {
                    min=conex[G[j].x];
                    max=conex[G[j].y];
                }
                else
                {
                    min=conex[G[j].y];
                    max=conex[G[j].x];
                }

                for (int k=1; k<=n; k++)
                    if (conex[k]==max)
                        conex[k]=min;

                poz=j+1;
                break;
            }

    //for (i=0; i<m; i++)
        //fout<<G[i].x<<" "<<G[i].y<<" "<<G[i].cost<<'\n';

    afisare();
    return 0;
}