#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int dim=2e5+5;
int n,m,t[dim],r[dim],len;
long long cost;
struct muc{
    int x,y,c;
}a[3*dim],sol[3*dim];
bool cmp(muc A, muc B){
    return A.c<B.c;
}
int rad(int nod){
    if(t[nod]==nod){
        return nod;
    }
    return (t[nod]=rad(t[nod]));
}
void uneste(int x, int y){
    if(r[x]<r[y]){
        t[x]=y;
        r[y]+=r[x];
    }
    else{
        t[y]=x;
        r[x]+=r[y];
    }
}
int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(int i=1;i<=n;i++){
        t[i]=i;
        r[i]=1;
    }
    for(int i=1;i<=m;i++){
        f>>a[i].x>>a[i].y>>a[i].c;
    }

    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        int r1=rad(a[i].x),r2=rad(a[i].y);
        if(r1!=r2){
            uneste(r1,r2);
            cost+=a[i].c;
            sol[++len]=a[i];
        }
    }
    g<<cost<<'\n'<<len<<'\n';
    for(int i=1;i<=len;i++){
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
    }
    return 0;
}