#include <fstream>
#include <vector>
#include <algorithm>
#define eb emplace_back
using namespace std;

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

struct muchie{
    int x, y, cost;
    muchie(int x, int y, int cost): x(x), y(y), cost(cost){}
};

int N, M, answercost;
vector<muchie> muchii, answer;
vector<int> grupa;

bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int find(int i){
    if(grupa[i] == i) return i;
    grupa[i] = find(grupa[i]);
    return grupa[i];
}

void unite(int i, int j){
    grupa[find(i)] = find(j);
}

int main() {
    in>>N>>M;
    for (int i = 1; i <= M; ++i) {
        int x, y, cost;
        in>>x>>y>>cost;
        muchii.eb(x,y,cost);
    }
    grupa.resize(N+1);
    for (int i = 1; i <= N; ++i) {
        grupa[i] = i;
    }
    sort(muchii.begin(), muchii.end(), cmp);
    for(auto& edg : muchii){
        if(find(edg.x) != find(edg.y)){
            answercost += edg.cost;
            unite(edg.x,edg.y);
            answer.eb(edg);
        }
    }
    out<<answercost<<'\n'<<N-1<<'\n';
    for(auto& edg : answer){
        out<<edg.x<<' '<<edg.y<<' '<<'\n';
    }
    return 0;
}