#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
        int nodX, nodY, cost;
        muchie(int x, int y, int c)
        {
                nodX = x;
                nodY = y;
                cost = c;
        }
        muchie() {}
};

struct el
{
        int x, y;
        el *next;
};

el *head, *p, *q;
muchie v[400005];
int n, m, arbore[200005], costTotal;
bool ok = false;

void Adaugare(int x, int y)
{
        if(head == NULL)
        {
                p = new el;
                p -> x = x;
                p -> y = y;
                p -> next = NULL;
                head = p;
        }
        else
        {
                q = new el;
                q -> x = x;
                q -> y = y;
                q -> next = NULL;
                p -> next = q;
                p = q;
        }
}

void Citire()
{
        f >> n >> m;
        for(int i = 1; i <= m; ++i)
        {
                int x, y, cost;
                f >> x >> y >> cost;
                v[i] = muchie(x, y, cost);
        }
}

void init_arb()
{
        for(int i = 1; i <= n; ++i) arbore[i] = i;
}

int root(int nod)
{
        if (arbore[nod] != nod) return root(arbore[nod]);
        return nod;
}

void Kruskal()
{
        int pas = 1, i = 0;
        while(pas < n)
        {
                ++i;
                int x = root(v[i].nodX);
                int y = root(v[i].nodY);
                if (x != y)
                {
                        ++pas;
                        Adaugare(v[i].nodX, v[i].nodY);
                        arbore[y] = x;
                        costTotal += v[i].cost;
                }
        }
}

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

void Afisare()
{
        g << costTotal << '\n' << n - 1 << '\n';
        for(p = head; p != NULL; p = p -> next)
                g << p -> x << " " << p -> y << '\n';
}

int main()
{
        Citire();
        init_arb();
        sort(v + 1, v + m + 1, cmp);
        Kruskal();
        Afisare();
        return 0;
}