#include <bits/stdc++.h>
using namespace std;
int n, m, T[200200], suma;
typedef struct{
    int a;
    int b;
    int v;
} leg;

leg A[400400], R[400400];

bool cmp(leg x, leg y){
    return x.v < y.v;
}

int find(int t){
    if(T[t] == t){
        return T[t];
    }

    T[t] = find(T[t]);
    return T[t];
}

void unite(int x, int y){
    T[find(x)] = find(y);
}

int main(){
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;

    for(int i=1; i<=n; i++){
        T[i] = i;
    }

    for(int i=1; i<=m; i++){
        cin >> A[i].a >> A[i].b >> A[i].v;
    }

    sort(A + 1, A + 1 + m, cmp);

    int rs= 0;
    for(int i=1; i<=m; i++){
        if(find(A[i].a) != find(A[i].b)){
            rs++;
            R[rs].a = A[i].a;
            R[rs].b = A[i].b;
            suma += A[i].v;
            unite(A[i].a, A[i].b);
        }
    }

    cout << suma << endl;

    cout << rs << endl;

    for(int i=1; i<=rs; i++){
        cout << R[i].a << ' ' << R[i].b << endl;
    }
    
}