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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int NMAX = 200005;
int N, M, tata[NMAX], rang[NMAX], cf;

struct edge{
    int u, v, cost;
};
vector<edge> edges, apm;
bool cmp(edge a, edge b){
    return a.cost < b.cost;
}

int find(int t){
    if(tata[t] == t)
        return t;
    return tata[t] = find(tata[t]);
}


int main(){
    f >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y, z;
        f >> x >> y >> z;
        edges.push_back({x, y, z});
    }

    for(int i = 1; i <= N; i++){
        tata[i] = i;
        rang[i] = 1;
    }

    sort(edges.begin(), edges.end(), cmp);
    for(int i = 0; i < edges.size(); i++){
        edge e = edges[i];
        int ru = find(e.u), rv = find(e.v);

        if(ru != rv){
            apm.push_back(e);
            cf += e.cost;

            if(rang[ru] < rang[rv])
                tata[ru] = tata[rv];
            else 
            if(rang[ru] > rang[rv])
                tata[rv] = ru;
            else{
                tata[rv] = ru;
                rang[ru]++;
            }
        }

        if(apm.size() >= N - 1)
            break;
    }

    g << cf << '\n';
    g << N - 1 << '\n';
    for(auto& e : apm)
        g << e.u << ' ' << e.v << '\n';

    return 0;
}