#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

typedef struct
{
   int x,y,cost;
} muchie;

int viz[200005], n, m, sum, poz, rankk[200005];
muchie v[400005], aux, finaly[400005];

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

int cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int findd(int i)
{
    while (viz[i] != i)
        i = viz[i];
    return i;
}

void afisare()
{
    ofstream g("apm.out");

    g << sum << "\n";
    g << n - 1 << "\n";
    for (int i = 1; i <= n - 1; i++)
        g << finaly[i].y << " " << finaly[i].x << "\n";
    g.close();
}

void unionn(int a, int b)
{
    if (rankk[a] < rankk[b])
        viz[a] = b;
    if (rankk[b] < rankk[a])
        viz[b] = a;
    if (rankk[a] == rankk[b])
    {
        viz[a] = b;
        rankk[b]++;
    }
}

int main()
{
    citire();
    sort(v + 1, v + m + 1, cmp);
    for (int i = 1; i <= n; i++)
        {
            viz[i] = i; rankk[i] = 1;
        }
    for (int i = 1; i <= m; i++)
    {
        int m_1 = findd(v[i].x);
        int m_2 = findd(v[i].y);

        if (m_1 != m_2)
        {
            poz++;
            unionn(m_1, m_2);
            finaly[poz].x = v[i].x;
            finaly[poz].y = v[i].y;
            sum += v[i].cost;
        }

    }
    afisare();
}