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

using namespace std;

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

vector<edge> solutie;

int n, m;
edge heap[MAXM];
int dim;
int p[MAXN], sz[MAXN];

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;
}

int find(int x){
    if(p[x]==x) return x;
    return find(p[x]);
}

bool sameComp(int a,int b){
    return find(a)==find(b);
}

void unionSets(int a, int b){
    int c1 = find(a), c2 = find(b);
    if(c1 == c2) return;
    if(sz[c1] >= sz[c2]){ sz[c1]+=sz[c2]; p[c2]=c1; }
    else{ sz[c2]+=sz[c1]; p[c1]=c2; }
}


void citire(){
    ifstream f("apm.in");
    f >> n >> m;
    for(int i=1;i<=n;i++){ p[i]=i; sz[i]=1; }
    edge muc;
    for(int i=0;i<m;i++){
        f >> muc.a >> muc.b >> muc.c;
        heap[++dim] = muc;
        upheap(dim);
    }
    f.close();
}

int main(){
    citire();
    edge muc;
    int cnt=0, sum=0;
    ofstream g("apm.out");
    while(cnt<n-1){
        muc = extractMin();
        if(!sameComp(muc.a, muc.b)){
            cnt++;
            sum+=muc.c;
            solutie.push_back(muc);
            unionSets(muc.a,muc.b);
        }
    }
    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;
}