#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2e5;
const int MMAX = 4e5;
int p[NMAX + 1];
int sz[NMAX + 1];

struct muchie {
    int x, y, c;
};

muchie v[MMAX + 1], sol[MMAX + 1];

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

//O(log* N)
int Find(int x) {//returneaza radacina arborelui in care se afla x
    // int r = x;
    // while(r != p[r]) {
    //     r = p[r];
    // }
    // int y = x;
    // while(y != r) {
    //     int d = p[y];
    //     p[y] = r;
    //     y = d;
    // }
    // return r;
    if(x == p[x]) {
        return x;
    }
    return p[x] = Find(p[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if(sz[x] < sz[y]) {
        swap(x, y);
    }
    p[y] = x;
    sz[x] += sz[y];
    sz[y] = 0;
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
	int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= m; i++) {
        cin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort(v + 1, v + m + 1, cmp);
    int sum = 0;
    int nr = 0;
    for(int i = 1; i <= m && nr < n - 1; i++) {
        if(Find(v[i].x) != Find(v[i].y)) {
            nr++;
            sol[nr] = v[i];
            sum += v[i].c;
            Union(v[i].x, v[i].y);
        }
    }
    cout << sum << '\n';
    cout << nr << '\n'; //n - 1
    for(int i = 1; i <= nr; i++) {
        cout << sol[i].x << ' ' << sol[i].y << '\n';
    }
}