#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 400001;

int N, M, COST;
int t[NMAX], rang[NMAX], ind[NMAX];

struct muchie
{
    int x, y, cost;
};
muchie m[NMAX];

bool compara(const muchie &m1, const muchie &m2)
{
    return m1.cost < m2.cost;
}

void citire()
{
    ifstream in ("apm.in");
    in >> N >> M;
    for (int i = 1; i <= M; ++i)
        in >> m[i].x >> m[i].y >> m[i].cost;
    in.close();
}

int tataNod(int nod) //cautarea se opreste cand tatal lui x e x
{
    int ceva = nod;

    while(t[nod] != nod)
        nod = t[nod];

    while(t[ceva] != ceva)      //dupa detm reprezentant fac compresie
    {
        int temp = t[ceva];
        t[ceva] = nod;
        ceva = temp;
    }

    return nod;
}

void unire(int x, int y)
{
    if(rang[x] < rang[y])
        t[x] = y;
    if(rang[y] < rang[x])
        t[y] = x;
    if(rang[x] == rang[y])
    {
        t[x] = y;
        rang[y]++;
    }
}

void kruskal()  //multimi disjuncte
{
    sort(m + 1, m + M + 1, compara);
    COST = 0;
    int n;
    n = N;
    for(int i = 1; i <= N; ++i)
        rang[i] = 1, t[i] = i;

    for(int i = 1; n > 1; ++i)        //N-1 muchii
    {
        int tata1 = tataNod(m[i].x);
        int tata2 = tataNod(m[i].y);

        if(tata1 != tata2)
        {
            ind[n] = i;                 //marchez muchia
            COST = m[i].cost + COST;
            unire(tata1, tata2);
            n--;
        }
    }
}

void afisare()
{
     ofstream out ("apm.out");
    out << COST << '\n' << N - 1 << '\n';
    for (int i = 2; i <= N; i++)
        out << m[ind[i]].x << ' ' << m[ind[i]].y << '\n';
    out.close();
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}