#include <stdio.h>
#include <set>
#define NMAX 200100
#include <vector>

using namespace std;

struct graf
{
    int dad, son, cost;
};

struct cmp
{
    bool operator() (const graf val1, const graf val2) const
    {
        return val1.cost < val2.cost;
    }
};


vector <graf> L[NMAX];
bool used [NMAX];
int minCost [NMAX], soldad[NMAX], solson[NMAX];
multiset <graf, cmp> Q;

inline graf mp (int x, int y, int z)
{
    graf now;

    now.dad = x; now.son = y; now.cost = z;
    return now;
}

int main ()
{
    int i, N, M, x, y, cost, sum = 0;
    vector <graf> :: iterator it;
    graf now, aux;

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

    scanf ("%d%d", &N, &M);
    for (i = 1; i <= N; i ++)
        minCost[i] = 1 << 30;
    for (i = 1; i <= M; i ++)
    {
        scanf ("%d%d%d", &x, &y, &cost);
        L[x].push_back (mp (x, y, cost));
        L[y].push_back (mp (y, x, cost));
    }

    used[1] = 1;
    for (it = L[1].begin (); it != L[1].end(); it ++)
    {
        now = *it;
        Q.insert (*it);
        if (now.cost < minCost [now.son])
            minCost [now.son] = now.cost;
    }

    for (i = 1; i < N; i ++)
    {
        now = *Q.begin ();
        if (used[now.son])
        {
            i --;
            Q.erase (Q.begin ());
            continue;
        }

        sum += now.cost;
        used[now.son] = 1;
        soldad[i] = now.dad; solson[i] = now.son;
        Q.erase (Q.begin ());
        for (it = L[now.son].begin (); it != L[now.son].end (); it ++)
        {
            aux = *it;
            if (!used[aux.son])
                if (aux.cost < minCost [aux.son])
                {
                    minCost [aux.son] = aux.cost;
                    Q.insert (*it);
                }
        }
    }

    printf ("%d\n%d\n", sum, N - 1);
    for (i = 1; i < N; i ++)
        printf ("%d %d\n", soldad[i], solson[i]);
    return 0;
}