#include <bits/stdc++.h>

using namespace std;

int ans1, n, m, ind[200001], T[200001], x[200001], y[200001], c[200001];
vector<int> v;

int grupa(int i) {
	if (T[i] == i)
        return i;
	T[i] = grupa(T[i]);
	return T[i];
}

void reuniune(int i, int j) {
	T[grupa(i)] = grupa(j);
}

bool tmp(int i, int j) {
    return c[i] < c[j];
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i] >> c[i];
        ind[i] = i;
    }
    sort(ind + 1, ind + m + 1, tmp);
    for(int i = 1; i <= n; i++)
        T[i] = i;
    for(int i = 1; i <= m; i++) {
        int val = ind[i];
        int xx = x[val], yy = y[val];
        if(grupa(xx) != grupa(yy)) {
            reuniune(xx, yy);
            ans1 += c[val];
            v.push_back(val);
        }
    }
    cout << ans1 << '\n' << n - 1 << '\n';
    for(auto i : v)
        cout << x[i] << ' ' << y[i] << '\n';

    return 0;
}