#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
int const NM = 4e5;
int t [1 + NM] , n , m  , Comp [1 + NM] , best;
int x [1 + NM] , y [1 + NM] , c [1 + NM];
inline bool fn (int a , int b){
    return c [a] < c [b];
}
vector <int> sol;
int comp (int node){
    if (node == Comp [node])
        return node;
    Comp [node] = comp (Comp [node]);
    return Comp [node];
}
ifstream f ("apm.in");
ofstream g ("apm.out");
int main (){
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++ i)
        f >> x [i] >> y [i] >> c [i] , t [i] = i;
    for(int i = 1 ; i <= n ; ++ i)
        Comp [i] = i;
    sort (t + 1 , t + m + 1 , fn);
    for(int i = 1 ; i <= m ; ++ i){
        if (comp (x [t [i]]) != comp (y [t [i]])){
            best += c [t [i]];
            Comp [comp (x [t [i]])] = comp (y [t [i]]);
            sol . push_back (t [i]);
        }
    }
    g << best << '\n' << -1 + n << '\n';
    for(auto i : sol)
        g << x [i] << ' ' << y [i] << '\n';
    return 0;
}