#include <cstdio>
#include <queue>
#include <algorithm>

#define Nmax 400005

using namespace std;

struct Muchie
{
    int x, y, c;
};

int N, M, T[Nmax], Cmin;
Muchie G[Nmax];
queue <pair <int, int> > Arbore;

bool Comp(Muchie a, Muchie b)
{
    if (a.c < b.c)
        return true;
    return false;
}

void Citire()
{
    int x, y, c;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
        scanf("%d %d %d", &G[i].x, &G[i].y, &G[i].c);
    sort(G + 1, G + M + 1, Comp);
    for (int i = 1; i <= N; ++i)
        T[i] = i;
}

int Caut_Tata(int nod)
{
    if (T[nod] != nod)
        T[nod] = Caut_Tata(T[nod]);
    return T[nod];
}

void APM()
{
    for (int i = 1; i <= M; ++i)
    {
        T[G[i].x] = Caut_Tata(G[i].x);
        T[G[i].y] = Caut_Tata(G[i].y);
        if (T[G[i].x] != T[G[i].y])
        {
            T[T[G[i].y]] = T[G[i].x];
            Cmin += G[i].c;
            Arbore.push(make_pair(G[i].x, G[i].y));
        }
    }
}

void Afisare()
{
    int x, y;
    printf("%d\n%d\n", Cmin, N - 1);
    while (!Arbore.empty())
    {
        x = Arbore.front().first;
        y = Arbore.front().second;
        Arbore.pop();
        printf("%d %d\n", x, y);
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    Citire();
    APM();
    Afisare();

    return 0;
}