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

using namespace std;

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

const int NMAX = 200005;

class Edge{
    public:
      int first, second;
      int weight;

      Edge(int from, int to, int wg){
          first = from;
          second = to;
          weight = wg;
      }
};

int N, M;
vector <Edge> V;
vector <Edge> solv;
int Ancestors[NMAX];
int Depths[NMAX];
int sol;

bool cmp(Edge a, Edge b){
    return (a.weight < b.weight);
}

void Read(){
    in >> N >> M;
    for(int i = 1; i <= N; ++i){
        Ancestors[i] = i;
        Depths[i] = 1;
    }
    for(int i = 1; i <= M; ++i){
        int a, b, c;
        in >> a >> b >> c;
        V.push_back(Edge(a, b, c));
    } 
}

int Root(int node){
    while(Ancestors[node] != node)
        node = Ancestors[node];
    return node;
}

void Unite(int first_root, int second_root){
    if(Depths[first_root] <= Depths[second_root]){
        Ancestors[first_root] = second_root;
        Depths[second_root] += Depths[first_root];
    }
    else{
        Ancestors[second_root] = first_root;
        Depths[first_root] += Depths[second_root];
    }
}

void Solve(){
    sort(V.begin(), V.end(), cmp);
    for(int i = 0; i < M; ++i){
        Edge edge = V[i];
        int root1 = Root(edge.first);
        int root2 = Root(edge.second);
        if(root1 != root2){
            Unite(root1, root2);
            sol += edge.weight;
            solv.push_back(edge);
        }
    }
}

void Print(){
    out << sol << "\n";
    out << solv.size() << "\n";
    for(vector<Edge>::iterator i = solv.begin(); i != solv.end(); ++i)
        out << (*i).first << " " << (*i).second << "\n";
}

int main(){
    Read();
    Solve();
    Print();
    return 0;
}