#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
FILE *f,*g;
int n,nedges,weigth;;
vector<pair<int,int> > tree;
struct disj{
    int p,d;
}nod[200001];

struct muchie{
   int x,y,w;
}dumm;
struct cmp{
    bool operator()(muchie a,muchie b){
        return a.w>b.w;
    }
};

priority_queue<muchie,vector<muchie>,cmp > edge;

int parent(int x){
    if (nod[x].p==x) return x;
    else nod[x].p=parent(nod[x].p);
    return nod[x].p;
}

void add(int x,int y){
    x=parent(x);
    y=parent(y);
    if (nod[x].d<nod[y].d) nod[x].p=y;
    else if (nod[x].d==nod[y].d) {nod[x].p=y;nod[y].d++;}
        else nod[y].p=x;
}
bool find(int x,int y){
    if (parent(x)==parent(y)) return 1;
    else return 0;
}

void find_tree(void){
    while(nedges<n-1){
        dumm=edge.top();
        while(find(dumm.x,dumm.y)){
            edge.pop();
            dumm=edge.top();
        }
        tree.push_back(make_pair(dumm.x,dumm.y));
        edge.pop();
        add(dumm.x,dumm.y);
        weigth+=dumm.w;
        nedges++;
    }
}

void read(void){
    int i,m;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&dumm.x,&dumm.y,&dumm.w);
        edge.push(dumm);
    }
}

int main(void){
    int i;
    read();
    for(i=1;i<=n;i++) nod[i].p=i;
    find_tree();
    fprintf(g,"%d\n%d\n",weigth,nedges);
    vector<pair<int,int> >::iterator it=tree.begin();
    while(it!=tree.end()){
        fprintf(g,"%d %d\n",it->first,it->second);
        it++;
    }
    return 0;
}