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

using namespace std;

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

struct muchie {
    int nod1;
    int nod2;
    int cost;
    bool operator <(const muchie &other)const{
        return cost > other.cost;
    }
};

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

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);
    depth.assign(n + 1, 1);
    for( int i = 1; i <= n; i++)
        father[i] = i;
    for(int i = 0; i < m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        muchii_date.push({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.top().nod1) != findrt(muchii_date.top().nod2)){
            unire(muchii_date.top().nod1, muchii_date.top().nod2);
            costTotal += muchii_date.top().cost;
            muchii.push_back(muchii_date.top());
        }
        muchii_date.pop();
    }
    cout << costTotal << '\n' << n - 1 << '\n';
    for(auto  muchie_crt : muchii){
        cout << muchie_crt.nod1 << ' ' << muchie_crt.nod2 << '\n';
    }
    return 0;
}