#include <fstream>
#include <cstring>

#define INF 0x7fffffff

#define gSize 200001
#define dSize 200001
#define TSize 200001
#define useSize 200001
#define heapSize 200001
#define posSize 200001
#define ughSize 200001

using namespace std;

ifstream in;
ofstream out;

struct graf
{
    int nod,cost;
    graf *link;
}*g[gSize];

int use[useSize];
int T[TSize];
int d[dSize];
int heap[heapSize];
int pos[posSize];
int ugh[ughSize];

int N,cnt=0;

inline void addedge(int x,int y,int c)
{
    graf *p=new graf;
    p->nod=y;
    p->cost=c;
    p->link=g[x];
    g[x]=p;
}

inline void HeapUp(int nod)
{
    int aux=heap[nod];

    for(;nod>1&&d[heap[nod>>1]]>d[aux];nod>>=1)
    {
        heap[nod]=heap[nod>>1];
        pos[heap[nod]]=nod;
    }

    heap[nod]=aux;
    pos[aux]=nod;
}

inline void HeapDown()
{
    int nod=1,L,R,aux=heap[1];

    while(1)
    {
        L=nod<<1;
        R=L+1;

        if(R<=heap[0]&&d[heap[L]]>d[heap[R]]&&d[aux]>d[heap[R]])
        {
            heap[nod]=heap[R];
            pos[heap[nod]]=nod;
            nod=R;
        }
        else
        if(L<=heap[0]&&d[heap[L]]<d[aux])
        {
            heap[nod]=heap[L];
            pos[heap[nod]]=nod;
            nod=L;
        }
        else
        {
            heap[nod]=aux;
            pos[aux]=nod;
            return;
        }
    }
}

inline void PopHeap()
{
    pos[heap[1]]=0;
    ugh[heap[1]]=0;
    heap[1]=heap[heap[0]];
    heap[heap[0]]=0;
    pos[heap[1]]=1;
    --heap[0];

    HeapDown();
}

inline void PushHeap(int nod)
{
    ++heap[0];
    heap[heap[0]]=nod;
    pos[nod]=heap[0];
    ugh[nod]=1;
}


inline void Prim()
{
    memset(ugh,0,sizeof(ugh));
    memset(use,0,sizeof(use));
    memset(T,0,sizeof(T));
    memset(heap,0,sizeof(heap));
    memset(pos,0,sizeof(pos));
    d[1]=-INF;
    for(int i=2;i<=N;++i) d[i]=INF;
    heap[0]=1;
    heap[1]=1;
    pos[1]=1;
    ugh[1]=1;

    for(int nod;heap[0];)
    {
        nod=heap[1];
        use[nod]=1;
        PopHeap();

        for(graf *p=g[nod];p;p=p->link)
            if(d[p->nod]>p->cost&&T[nod]!=p->nod)
            {
                if(!ugh[p->nod]) PushHeap(p->nod);
                HeapUp(pos[p->nod]);
                T[p->nod]=nod;
                d[p->nod]=p->cost;
            }
    }
}

int main()
{
    int M,x,y,c;
    in.open("apm.in");

    in>>N>>M;
    for(;M--;)
    {
        in>>x>>y>>c;
        addedge(x,y,c);
        addedge(y,x,c);
    }

    in.close();

    Prim();

    out.open("apm.out");

    for(int i=2;i<=N;++i) cnt+=d[i];

    out<<cnt<<'\n'<<N-1<<'\n';
    for(int i=2;i<=N;++i)
        out<<T[i]<<' '<<i<<'\n';

    out.close();

    return 0;
}