#include <iostream>
#include <vector>

#define NMax 200005
#define v first
#define c second
#define Inf 2000000000

using namespace std;

vector < pair <int, int> > G[NMax];
int N, Prim[NMax], Heap[NMax], NHeap, Poz[NMax], Father[NMax], CostAPM;

void Read ()
{
    freopen ("apm.in", "r", stdin);
    int M;
    scanf ("%d %d", &N, &M);
    for (; M>0; --M)
    {
        int X, Y, Z;
        scanf ("%d %d %d", &X, &Y, &Z);
        G[X].push_back (make_pair (Y, Z));
        G[Y].push_back (make_pair (X, Z));
    }
}

void Print ()
{
    freopen ("apm.out", "w", stdout);
    printf ("%d\n%d\n", CostAPM, N-1);
    for (int i=2; i<=N; ++i)
    {
        printf ("%d %d\n", Father[i], i);
    }
}

inline void Swap (int X, int Y)
{
    int Aux;
    Aux=Poz[Heap[X]];
    Poz[Heap[X]]=Poz[Heap[Y]];
    Poz[Heap[Y]]=Aux;
    Aux=Heap[X];
    Heap[X]=Heap[Y];
    Heap[Y]=Aux;
}

void Percolate (int X)
{
    int F=X/2;
    while (F>0)
    {
        if (Prim[Heap[X]]<Prim[Heap[F]])
        {
            Swap (X, F);
            X=F;
            F=X/2;
        }
        else
        {
            return;
        }
    }
}

void Sift (int X)
{
    int Son=2*X;
    while (Son<=NHeap)
    {
        if (Son+1<=NHeap and Prim[Heap[Son+1]]<Prim[Heap[Son]])
        {
            ++Son;
        }
        if (Prim[Heap[Son]]<Prim[Heap[X]])
        {
            Swap (X, Son);
            X=Son;
            Son=2*X;
        }
        else
        {
            return;
        }
    }
}

void Delete (int X)
{
    Swap (X, NHeap);
    Poz[Heap[NHeap]]=-1;
    --NHeap;
    Sift (X);
}

void Initialize ()
{
    NHeap=N;
    for (int i=1; i<=N; ++i)
    {
        Heap[i]=i;
        Prim[i]=Inf;
        Poz[i]=i;
    }
    Prim[1]=0;
}

void APM ()
{
    Initialize ();
    while (NHeap>0)
    {
        int X=Heap[1];
        Delete (1);
        for (unsigned i=0; i<G[X].size (); ++i)
        {
            int V=G[X][i].v;
            int C=G[X][i].c;
            if (Poz[V]!=-1 and C<Prim[V])
            {
                Father[V]=X;
                Prim[V]=C;
                Percolate (Poz[V]);
            }
        }
    }
}

int main()
{
    Read ();
    APM ();
    for (int i=2; i<=N; ++i)
    {
        CostAPM+=Prim[i];
    }
    Print ();
    return 0;
}