#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

vector<int> parent, height;
typedef tuple<int, int, int> tiii;
vector<tuple<int, int, int>> edges;
vector<pair<int, int>> sol;
int n, m, x, y, c;

int rep(int x) {
    if (!parent[x])
        return x;
    
    int reprez = rep(parent[x]);
    parent[x] = reprez;
    return reprez;
}

void myUnion (int x, int y) {
    int repx = rep(x), repy = rep(y);

    if (height[repx] < height[repy])
        parent[repx] = repy;

    else if (height[repy] < height[repx])
        parent[repy] = repx;

    else {
        parent[repx] = repy;
        ++ height[repy];
    }
}

bool cmp(tiii a, tiii b) {
    return get<0>(a) < get<0>(b);
}

int main() {
    in >> n >> m;
    parent.resize(n + 1, 0);
    height.resize(n + 1, 0);

    while(m --) {
        in >> x >> y >> c;
        edges.push_back({c, x, y});
    }

    sort(edges.begin(), edges.end(), cmp);

    int totalCost = 0;
    for(auto edge : edges) {
        int node1 = get<1>(edge), node2 = get<2>(edge), cost = get<0>(edge);
        if(rep(node1) == rep(node2))
            continue;
        
        myUnion(node1, node2);
        totalCost += cost;
        sol.push_back({node1, node2});
    }

    out << totalCost << '\n' << sol.size() << '\n';

    for(auto edge : sol) 
        out << edge.first << ' ' << edge.second << '\n';
    
    return 0;
}