#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int maxn=400100;
int GR[maxn], X[maxn], Y[maxn], C[maxn];
int N, M, ANS, IND[maxn];
vector <int> VANS;
int grupa(int i) {
    if (GR[i]==i){
        return i;
    }
    GR[i]=grupa(GR[i]);
    return GR[i];
}
void reuniune(int i, int j) {
    GR[grupa(i)]=grupa(j);
}
bool cmpf(int i, int j) {
    return(C[i]<C[j]);
}
int main() {
    f>>N>>M;
    for (int i=1; i<=M; i++) {
        f>>X[i]>>Y[i]>>C[i];
        IND[i]=i;
    }
    for (int i=1; i<=N; i++){
        GR[i]=i;
    }
    for (int i=1; i<=N; i++){
        GR[i]=i;
    }
    sort(IND+1, IND+M+1, cmpf);
    for (int i=1; i<=M; i++) {
        if (grupa(X[IND[i]])!=grupa(Y[IND[i]])) {
            ANS+=C[IND[i]];
            reuniune(X[IND[i]], Y[IND[i]]);
            VANS.pb(IND[i]);
        }
    }
    g<<ANS<<'\n';
    g<<N-1<<'\n';
    for (int i=0; i<N-1; i++){
        g<<X[VANS[i]]<<" "<<Y[VANS[i]]<<'\n';
    }
    return 0;
}