/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on February 5, 2010, 5:52 PM
 */
#include <fstream>
#define Nmax 200000
#define inf 0x3f3f3f3f

/*
 *
 */
using namespace std;
struct vertex
{
    int y, c;
    vertex* next;
} *L[Nmax];
typedef vertex *list;
int N;
int Heap[Nmax], Position[Nmax], cmin[Nmax], apm[Nmax];
inline void push( int x, int y, int c )
{
    list q;
    q=new vertex;
    q->y=y; q->c=c;
    q->next=L[x];
    L[x]=q;
}
inline void swap( int& x, int& y )
{
    int aux=x;
    x=y;
    y=aux;
}
void DownHeap( int k )
{
    int son;
    while( true )
    {
        son=2*k;
        if( son > N )
            return;
        if( 2*k+1 <= N && cmin[Heap[son]] > cmin[Heap[2*k+1]] )
            son=2*k+1;
        if( cmin[Heap[son]] >= cmin[Heap[k]] )
            return;
        swap( Heap[son], Heap[k] );
        swap( Position[Heap[son]], Position[Heap[k]] );
        k=son;
    }
}
void UpHeap( int k )
{
    int key=cmin[Heap[k]], f=k/2;
    while( k > 1 && key < cmin[Heap[f]] )
    {
        swap( Heap[k], Heap[f] );
        swap( Position[Heap[k]], Position[Heap[f]] );
        k=f;
        f=k/2;
    }
}
void cut_root()
{
    swap( Position[Heap[1]], Position[Heap[N]] );
    Position[Heap[1]]*=-1;
    swap( Heap[1], Heap[N] );
    --N;
    DownHeap(1);
}
void insert( int vertex, int value )
{
    Heap[++N]=vertex;
    Position[vertex]=N;
    cmin[vertex]=value;
    UpHeap( N );
}
int main( void )
{
    list p;
    int n, m, x, y, c, vertex, s=0;
    ifstream in("apm.in");
    in>>n>>m;
    for( x=0; x < n; ++x )
        cmin[x]=inf;
    for( ; m; --m )
    {
        in>>x>>y>>c;
        x-=1; y-=1;
        push( x, y, c );
        push( y, x, c );
        if( !x )
            insert( y, c );
        else if( !y )
                insert( x, c );
    }
    Position[0]=-1;
    for( m=n-1; m; --m )
    {
        vertex=Heap[1];
        s+=cmin[vertex];
        cut_root();
        for( p=L[vertex]; p; p=p->next )
        {
            if( !Position[p->y] )
                apm[p->y]=vertex, insert( p->y, p->c );
            else if( Position[p->y] > 0 && cmin[p->y] > p->c )
                 {
                        apm[p->y]=vertex;
                        cmin[p->y]=p->c;
                        UpHeap( Position[p->y] );
                 }
        }
    }
    ofstream out("apm.out");
    out<<s<<' '<<(n-1)<<'\n';
    for( x=1; x < n; ++x )
        out<<(x+1)<<' '<<(apm[x]+1)<<'\n';
    return 0;
}