#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int N=200001;
const int M=400001;

int n,m,tata[N],cost,rez,nrcomp;

struct edge{
    int x,y,cost;
}muchii[M],solutie[M];

void citire(){
    int i;
    in>>n>>m;
    for(i=1;i<=m;++i){
        in>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
    }
}

inline bool funct(edge a,edge b){
    if(a.cost<b.cost)
        return true;
    return false;
}

inline int root(int a){
    int ca,rad;
    ca=a;
    while(a!=tata[a])
        a=tata[a];
    rad=tata[a];
    a=ca;
    int b=a;
    while(a!=tata[a]){
        b=a;
        a=tata[a];
        tata[b]=rad;
    }
    return rad;
}

void rezolvare(){
    int a,b,c,i,tataa,tatab;
    sort(&muchii[1],&muchii[m+1],funct);
    for(i=1;i<=m;i++){
        a=muchii[i].x;
        b=muchii[i].y;
        c=muchii[i].cost;
        tataa=root(a);
        tatab=root(b);
        if(tataa!=tatab){
            rez++;
            solutie[rez].x=a;
            solutie[rez].y=b;
            tata[tataa]=tatab;
            cost+=c;
        }
    }
}

void afisare(){
    int i;
    out<<cost<<"\n";
    out<<rez<<"\n";
    for(i=1;i<=rez;i++){
        out<<solutie[i].x<<" "<<solutie[i].y<<"\n";
    }
}

int main(){
    citire();
    for(int i=1;i<=n;i++){
        tata[i]=i;
    }
    rezolvare();
    afisare();
    return 0;
}