#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
    int x, y, c;
};
muchie v[400001];
int sef[200001], dim[200001], sol[200001];
int gasire_sef(int x){
    if(sef[x] != x){
        sef[x] = gasire_sef(sef[x]);
    }
    return sef[x];
}
bool cmp(muchie a, muchie b){
    return a.c < b.c;
}
int main()
{
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m ; i++){
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; i++){
        sef[i] = i;
        dim[i] = 1;
    }
    int nr = 0;
    int costt = 0;
    for(int i = 1; i <= m && nr < n - 1; i++){
        int a = gasire_sef(v[i].x);
        int b = gasire_sef(v[i].y);
        if(a != b){
            if(dim[a] < dim[b]){
                swap(a, b);
            }
            sef[b] = a;
            dim[a] += dim[b];
            costt += v[i].c;
            nr++;
            sol[nr] = i;
        }
    }
    fout << costt << "\n";
    fout << nr << "\n";
    for(int i = 1; i <= nr; i++){
        fout <<v[sol[i]].y << " " << v[sol[i]].x << "\n";
    }
    return 0;
}