#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int cost_min, nr_muchii;

struct muchii {
    int nod1, nod2;
} v_muchii[400001];

struct cost {
    int nod1, nod2, c;
} v_cost[400001];

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

int daddy[200001], depth[200001];

int find_daddy(int nod) {
    if(nod == daddy[nod])
        return daddy[nod];
    return daddy[nod]=find_daddy(daddy[nod]);
}

void unire(int nod1, int nod2) {
    nod1 = find_daddy(nod1);
    nod2 = find_daddy(nod2);

    if(depth[nod1] > depth[nod2])
        daddy[nod2] = nod1;
    else if(depth[nod1] < depth[nod2])
        daddy[nod1] = nod2;
    else {
        daddy[nod1] = nod2;
        depth[nod2]++;
    }
}

int main() {

    int n , m;
    cin >> n >> m;

    for(int i = 1 ; i <= m ; i++) {
        cin >> v_cost[i].nod1 >> v_cost[i].nod2 >> v_cost[i].c;
    }

    sort(v_cost + 1, v_cost + m + 1, cmp);

    for(int i = 1 ; i <= n ; i++)
        daddy[i] = i;

    for(int i = 1 ; i <= m ; i++)
        if(find_daddy(v_cost[i].nod1) != find_daddy(v_cost[i].nod2)) {
            nr_muchii++;
            v_muchii[nr_muchii].nod1 = v_cost[i].nod1;
            v_muchii[nr_muchii].nod2 = v_cost[i].nod2;
            cost_min += v_cost[i].c;
            unire(v_cost[i].nod1, v_cost[i].nod2);
        }

    cout << cost_min << '\n' << nr_muchii << '\n';
    for(int i = 1 ; i <= nr_muchii; i++)
        cout << v_muchii[i].nod1 << " " << v_muchii[i].nod2 << '\n';
    return 0;
}