#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]);
}
bool comp(graf a, graf b){
    return a.z < b.z;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> M[i].x >> M[i].y >> M[i].z;
    }
    sort(M+1,M + m + 1, comp);

    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;
}