#include <fstream>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n, m, k, cnt, t[20001];
struct graf{
    int x, y, z;
}M[400001];
graf v[400001];
int radacina(int a){
    if(a == t[a]) return a;
    else return t[a] = radacina(t[a]);
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> M[i].x >> M[i].y >> M[i].z;
    }
    for(int i = 1; i < m; ++i){
        for(int j = i + 1; j <= m; ++j){
            if(M[i].z > M[j].z){
                swap(M[i],M[j]);
            }
        }
    }
    for(int i = 1; i <= n; ++i) t[i] = i;
    int s = 0, r1, r2;

    for(int i = 1; i <= m; ++i){
        r1 = radacina(t[M[i].x]);
        r2 = radacina(t[M[i].y]);
        if(r1 != r2){
            v[++cnt] = M[i];
            s += M[i].z;
            t[r1] = t[r2];
        }
    }
    cout << s << '\n';
    cout << cnt << '\n';
    for(int i = 1; i <= cnt; ++i){
        cout << v[i].y << " " << v[i].x << '\n';
    }
    return 0;
}