#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
typedef int i32;
struct graf{
    int nod1, nod2, cost;
} g[400001];

i32 n, m, c[200001], a[400001], nrc, hcost;

bool fmt(graf a, graf b){
    if(a.cost > b.cost) return 0;
    return 1;
}

int rad(int nod){
    if(nod == c[nod]) return nod;
    else return c[nod] = rad(c[nod]);
}
void kruskal(){
    
    for(int i = 1; i <= m; i++){
        
        i32 r1 = rad(g[i].nod1);
        i32 r2 = rad(g[i].nod2);
        
        if(r1 != r2){
            a[++nrc] = i;
            hcost += g[i].cost;
            c[r1] = c[r2];
        }
    }
}
int main() {
    
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> g[i].nod1 >> g[i].nod2 >> g[i].cost;
    sort(g + 1, g + 1 + m, fmt);
    for(int i = 1; i <= n; i++) c[i] = i;
    
    kruskal();
    cout << hcost << '\n';
    cout << nrc << '\n';
    for(int i = 1; i <= nrc; i++)
        cout << g[a[i]].nod1 <<" "<< g[a[i]].nod2 <<'\n';
}