#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int Nmax = 200005;
const int Mmax = 400005;
int T[Nmax],r[Nmax];
int N,M;
int Query(int x){
    int R,y;
    for(R=x;R!=T[R];R=T[R]);
    for(;x!=T[x];){
        y=T[x];
        T[x]=R;
        x=y;
    }
    return R;
}
void Unite(int x,int y){
    if(r[x]>r[y]){
        T[y]=x;
        if(r[x]==r[y]) r[x]++;
    }
    else{
        T[x]=y;
    }
}
struct query{
    int a,b,c;
} q[Mmax],Arb[Mmax];int K;
bool cmp(query x,query y){
    return x.c<y.c;
}
int main(){
    in>>N>>M;
    for(int i=1;i<=N;i++){
        T[i]=i;
        r[i]=1;
    }
    for(int i=1;i<=M;i++){
        in>>q[i].a>>q[i].b>>q[i].c;
    }
    sort(q+1,q+M+1,cmp);
    for(int i=1;i<=M;i++){
        int A=Query(q[i].a),B=Query(q[i].b);
        if(A!=B){
            Unite(A,B);
            Arb[++K]=q[i];
        }
    }
    int sum=0;
    for(int i=1;i<=K;i++){
        sum+=Arb[i].c;
    }
    out<<sum<<'\n'<<K<<'\n';
    for(int i=1;i<=K;i++){
        out<<Arb[i].a<<' '<<Arb[i].b<<'\n';
    }
    return 0;
}