#include <fstream>
#define nmax 200000
using namespace std;

struct list{
    int v, cost;
    list *next;
} *L[nmax];

int N;
int Heap[nmax], Position[nmax], cmin[nmax], apm[nmax];

inline void push(int x,int y,int c)
{
    list *q;
    q=new list;
    q->v=y;
    q->cost=c;
    q->next=L[x];
    L[x]=q;
}
void DownHeap(int k)
{
    int son;
    while(true)
    {
        son=2*k;
        if(son>N)
            return;
        if(son<N && cmin[Heap[son]]>cmin[Heap[son+1]])
            ++son;
        if(cmin[Heap[son]]>=cmin[Heap[k]])
            return;
        swap(Heap[k],Heap[son]);
        swap(Position[Heap[k]],Position[Heap[son]]);
        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/=2;
    }
}
void cut_root()
{
    swap(Heap[1],Heap[N]);
    swap(Position[Heap[1]],Position[Heap[N]]);
    Position[Heap[N]]=-1;
    --N;
    DownHeap(1);
}
void insert(int v, int value)
{
    Heap[++N]=v;
    cmin[v]=value;
    Position[v]=N;
    UpHeap(N);
}
int main(void)
{
    list *p;
    int n,m,x,y,c,w,s=0;
    ifstream in("apm.in");
    in>>n>>m;
    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=1;m<n;++m){
        w=Heap[1];
        s+=cmin[w];
        cut_root();
        for(p=L[w];p;p=p->next){
            if(-1==Position[p->v])
                continue;
            if(0 == Position[p->v] )
              apm[p->v]=w,  insert(p->v,p->cost);
            else if(cmin[p->v]>p->cost){
                    apm[p->v]=w;
                    cmin[p->v]=p->cost;
                    UpHeap(Position[p->v]);
                }
        }
    }
    ofstream out("apm.out");
    out<<s<<' '<<(n-1)<<'\n';
    for(x=1;x<n;++x)
        out<<(x+1)<<' '<<(apm[x]+1)<<'\n';
    return 0;
}