#include <bits/stdc++.h>
#define DIM 200005

using namespace std;

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

int n, m, i, rx, ry, sol1, cnt;
int t[DIM], vec[2*DIM];

struct checPufos {
    int x, y, c;
} ;

checPufos v[2*DIM];

inline bool cmp (const checPufos &a, const checPufos &b){
    return a.c < b.c;
}

inline int rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

int main(){
    fin >> n >> m;
    for (i=1; i<=m; i++){
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    for (i=1; i<=n; i++)
        t[i] = -1;
    sort (v + 1, v + m + 1, cmp);
    for (i=1; i<=m; i++){
        rx = rad (v[i].x), ry = rad (v[i].y);
        if (rx != ry){
            vec[++cnt] = i;
            sol1 += v[i].c;
            if (t[rx] < t[ry]){
                t[rx] += t[ry];
                t[ry] = rx;
            }
            else{
                t[ry] += t[rx];
                t[rx] = ry;
            }
        }
    }
    fout << sol1 << "\n" << n - 1 << "\n";
    for (i=1; i<=cnt; i++)
        fout << v[vec[i]].y << " " << v[vec[i]].x << "\n";
    return 0;
}