#include<fstream>
#include<algorithm>

using namespace std;

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

int N,M,Nr,A[200005],X[400005],Y[400005],V[200005],Sol,P[400005],C[400005];

int Radacina(int K){
    if(A[K]==0)
        return K;
    A[K]=Radacina(A[K]);
    return A[K];
}

void Unire(int i,int j){
    A[Radacina(i)]=Radacina(j);
}

bool Comp(int i,int j){
    return C[i]<C[j];
}

int main(){
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X[i]>>Y[i]>>C[i];
        P[i]=i;
    }
    sort(P+1,P+M+1,Comp);
    for(int i=1;i<=M;i++)
        if(Radacina(X[P[i]])!=Radacina(Y[P[i]]))
        {
            Sol=Sol+C[P[i]];
            Unire(X[P[i]],Y[P[i]]);
            V[Nr]=P[i];
            Nr++;
        }
    N--;
    fout<<Sol<<"\n"<<N<<"\n";
    for(int i=0;i<N;i++)
        fout<<X[V[i]]<<" "<<Y[V[i]]<<"\n";
    return 0;
}