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

using namespace std;

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

struct muchie {
    int nod1;
    int nod2;
    int cost;
};

int costTotal;
vector <int> father, depth;
vector <muchie> muchii_date, muchii;

int findrt(int node){
    if(node == father[node])
        return node;
    else
        return father[node] = findrt(father [node]);
}

void unire(int node1, int node2){
    node1 = findrt(node1);
    node2 = findrt(node2);
    if(depth[node1] > depth[node2]){
        father[node2] = node1;
    }
    else if(depth[node1] < depth[node2]){
        father[node1] = node2;
    }
    else{
        father[node2] = node1;
        depth[node1]++;
    }
}

bool cmp(muchie x, muchie y){
    return x.cost < y.cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    father.resize(n + 1);
    for( int i = 1; i <= n; i++)
        father[i] = i;
    depth.assign(n + 1, 1);
    for(int i = 0; i < m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        muchii_date.push_back({x, y, c});
    }
    sort(muchii_date.begin(), muchii_date.end(), cmp);
    for(int i = 0; i < m and muchii.size() <= n; i++){
        if(findrt(muchii_date[i].nod1) != findrt(muchii_date[i].nod2)){
            unire(muchii_date[i].nod1, muchii_date[i].nod2);
            costTotal += muchii_date[i].cost;
            muchii.push_back(muchii_date[i]);
        }
    }
    cout << costTotal << '\n' << n - 1 << '\n';
    for(int i = 0; i < muchii.size(); i++){
        cout << muchii[i].nod1 << ' ' << muchii[i].nod2 << '\n';
    }
    return 0;
}