#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, nr_muchii;

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

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;
}

void afisare()
{
    int i;

    fout<<C_apm<<'\n';
    fout<<nr_muchii<<'\n';

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

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

    int min, max;

    for (int i=0; i<m ; i++)
    {
        if (conex[G[i].x] != conex[G[i].y] )
        {

            apm[++nr_muchii]=i;
            C_apm+=G[i].cost;

            if (conex[G[i].x] < conex[ G[i].y])
            {
                min=conex[G[i].x];
                max=conex[G[i].y];
            }
            else
            {
                min=conex[G[i].y];
                max=conex[G[i].x];
            }

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

    afisare();
    return 0;
}