#include <fstream>
#define MAXN 200001
#define MAXM 400001
#include <vector>

using namespace std;

typedef struct edge{
    int a, b, c;
}edge;

typedef struct list{
    int nod, cost;
    list* next;
}list;

vector<edge> solutie;
list* graf[MAXN];

int n, m;
edge heap[MAXM];
bool viz[MAXN];
bool disc[MAXN];
int dim;


void swap(edge &a,edge &b){ edge c=a; a=b; b=c; }

void upheap(int poz){
    if(poz==1) return;
    int p = poz/2;
    if(heap[poz].c < heap[p].c){
        swap(heap[poz],heap[p]);
        upheap(p);
    }
}

void downheap(int poz){
    int f1 = poz*2;
    int f2 = poz*2+1;
    int min = poz;
    if(f1<=dim) if(heap[f1].c < heap[poz].c) min = f1;
    if(f2<=dim) if(heap[f2].c < heap[min].c) min = f2;
    if(min!=poz){
        swap(heap[min],heap[poz]);
        downheap(min);
    }
}

edge extractMin(){
    edge min = heap[1];
    swap(heap[1],heap[dim]);
    dim--;
    downheap(1);
    return min;
}


void citire(){
    ifstream f("apm.in");
    f >> n >> m;
    int from, to, cost;
    for(int i=0;i<m;i++){
        f >> from >> to >> cost;
        list *p = new list; p->nod = to; p->cost = cost; p->next = graf[from]; graf[from]=p;
        list *q = new list; q->nod = from; q->cost = cost; q->next = graf[to]; graf[to]=q;
    }
    f.close();
}

int main(){
    citire();
    edge muc;
    int cnt=0, sum=0;
    ofstream g("apm.out");
    int cur=1;
    while(cnt<n-1){
        viz[cur]=true;
        cnt++;
        list *p = graf[cur];
        while(p){
            if(!viz[p->nod]){
                muc.a = cur; muc.b = p->nod; muc.c = p->cost;
                heap[++dim] = muc;
                upheap(dim);
            }
            p = p->next;
        }
        do{
            muc = extractMin();
        }while(dim && ((viz[muc.b]&&viz[muc.a])||(!viz[muc.b]&&!viz[muc.a])));

        solutie.push_back(muc);
        //if(!(!viz[muc.a]^!viz[muc.b])) continue;
        cur = muc.b;
        sum += muc.c;
    }
    g << sum << endl << (n-1) << endl;
    for(vector<edge>::iterator it=solutie.begin();it!=solutie.end();it++) g<<it->a << ' ' << it->b << endl;
    g.close();
    return 0;
}