#include<bits/stdc++.h>
using namespace std;
struct muchie{
    int x,y,c;
}A[400001],sol[400001];
int N,M,T[400001],P[400001];
bool cmp(muchie X,muchie Y){
    if(X.c>Y.c)return false;
    return true;
}
int Root(int x){
    while(x!=T[x])x=T[x];
    return x;
}
void Unifica(int x,int y){
    if(P[x]<P[y])T[x]=y;
    if(P[x]>P[y])T[y]=x;
    if(P[x]==P[y]){
        T[y]=x;
        P[x]++;
    }
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i){
        scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].c);
        T[i]=i;
    }
    sort(A+1,A+M+1,cmp);
    int i=1,k=0,ct=0;
    while(k<N-1){
        int rx=Root(A[i].x);
        int ry=Root(A[i].y);
        if(rx!=ry){
            ++k;
            ct+=A[i].c;
            sol[k]=A[i];
            Unifica(rx,ry);
        }
        ++i;
    }
    printf("%d\n%d\n",ct,k);
    for(int i=1;i<=k;++i)printf("%d %d\n",sol[i].y,sol[i].x);
    return 0;
}