#include <fstream>
#include <algorithm>
#define MMAX 400000
#define NMAX 200000

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

int n, m, nr_muchii_arbore;

struct Muchie
{
    int x, y;
   int c;
};
Muchie G[MMAX];

int APM[NMAX], conex[MMAX];
int cost_APM;

void citire();
bool compara(Muchie a, Muchie b);

int main()
{
    int i, j, c, C;
    citire();
    for(i = 0; i < m && nr_muchii_arbore < n ; i++)
    {
        if(conex[G[i].x] != conex[G[i].y])
        {
            if(conex[G[i].x] < conex[G[i].y])
            {
                c = conex[G[i].x];
                C = conex[G[i].y];
            }
            else
            {
                c = conex[G[i].y];
                C = conex[G[i].x];
            }

            APM[++nr_muchii_arbore] = i;
            cost_APM = cost_APM + G[i].c;

            for(j = 1; j <= n; ++j)
            {
                if(conex[j] == C)
                    conex[j] = c;
            }
        }
    }

    fout << cost_APM;
    fout << '\n';
    fout << nr_muchii_arbore;
    fout << '\n';
    for(i = 1; i <= n-1; ++i)
        fout << G[APM[i]].x << ' ' << G[APM[i]].y << '\n';
    return 0;
}

void citire()
{
    int i;
    fin >> n >> m;
    for(i = 0 ; i < m; ++i)
        fin >> G[i].x >> G[i].y >> G[i].c;
    for(i = 1; i <= n; ++i)
        conex[i] = i;
    sort(G, G+m, compara);

    /*
    for(i = 1 ;i<=m; ++i)
        fout<<G[i].x<<" "<<G[i].y<<" "<<G[i].c<<"\n";
    */
}

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