#include <fstream>
#include <cstdio>
#include <algorithm>

using namespace std;

FILE *fin = fopen ("apm.in", "r");
ofstream fout ("apm.out");

int n, m;
struct muchie {int x, y, c;} M[400010];

int compare (const muchie &a, const muchie &b)
{
    return a.c < b.c;
}

int m_disjuncte[200010], inaltime[200010];



void Union (int rad1, int rad2) // unesc radacinile a 2 lanturi in functie de inaltime
{
    if (inaltime[rad1] < inaltime[rad2]) m_disjuncte[rad1] = rad2;
    else if (inaltime[rad2] < inaltime[rad1]) m_disjuncte[rad2] = rad1;
        else
        {
            m_disjuncte[rad1] = rad2;
            ++inaltime[rad2];
        }
}



int radacina (int x) // find root + comprimare
{
    int cx = x;
    while (cx != m_disjuncte[cx]) // inca nu am ajuns la radacina
        cx = m_disjuncte[cx];
    // cx = radacina

    // comprimam drumul
    int aux;
    while (m_disjuncte[x] != cx)
    {
        aux = m_disjuncte[x];
        m_disjuncte[x] = cx;
        x = aux;
    }
    return cx;
}

int apm[200010][3], contor;

int main()
{
    fscanf (fin, "%d %d", &n, &m);
    int i, cost_minim = 0;
    for (i = 1; i <= m; i++) fscanf (fin, "%d %d %d", &M[i].x, &M[i].y, &M[i].c);
    sort (M+1, M+m+1, compare); // am sortat vectorul muchiilor (M) crescator dupa costuri

    for (i = 1; i <= n; i++) m_disjuncte[i] = i;
    for (i = 1; i <= m; i++)
    {
        int rad1 = radacina (M[i].x); // radacina din nodul x
        int rad2 = radacina (M[i].y);
        if (rad1 != rad2)
        {
            Union (rad1, rad2);
            cost_minim += M[i].c;
            apm[++contor][1] = M[i].x;
            apm[contor][2] = M[i].y;
        }
    }

    fout << cost_minim << '\n';
    fout << contor << '\n';
    for (i = 1; i <= contor; i++) fout << apm[i][1] << ' ' << apm[i][2] << '\n';
    return 0;
}