#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define DIM 200005

int N, M;
int tata[DIM], h[DIM];

vector <pair <int, pair <int, int> > > Muchii;
vector <pair <int, int> > Alese;

int Find(int x);
void Union(int x, int y);

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d\n", &N, &M);

    for(int i = 1; i <= M; ++i) {
        int x, y, cost;

        scanf("%d %d %d\n", &x, &y, &cost);

        Muchii.push_back(make_pair(cost, make_pair(x, y)));
    }

    sort(Muchii.begin(), Muchii.end());

    int CostFinal = 0;

    for(unsigned int z = 0; z < Muchii.size(); ++z) {
        int rx = Find(Muchii[z].second.first);
        int ry = Find(Muchii[z].second.second);
        if(rx == ry) {
            continue;
        }

        CostFinal += Muchii[z].first;
        Alese.push_back(make_pair(Muchii[z].second.first, Muchii[z].second.second));
        Union(rx, ry);
    }

    cout << CostFinal << '\n';
    cout << Alese.size() << '\n';

    for(unsigned int z = 0; z < Alese.size(); ++z) {
        cout << Alese[z].first << ' ' << Alese[z].second << '\n';
    }

    return 0;
}

int Find(int x) {
    int rx = x;

    while(tata[rx]) {
        rx = tata[rx];
    }

    while(x != rx) {
        int y = tata[x];
        tata[x] = rx;
        x = y;
    }

    return rx;
}

void Union(int x, int y) {
    int rx = Find(x);
    int ry = Find(y);

    if(h[rx] > h[ry]) {
        tata[ry] = rx;
    }
    else {
        tata[rx] = ry;
    }

    if(h[rx] == h[ry]) {
        ++h[ry];
    }
}