#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 200000 + 5;
const int MMAX = 2 * NMAX;

struct Edge {
    int a, b, c;
    bool operator<(const Edge &arg) const {
        return c < arg.c;
    }
} edges[MMAX];

int N, M;
int father[NMAX];
int h[NMAX];

void init() {
    for (int i = 1; i <= N; ++ i)
        father[i] = i;
}

int find(int node) {
    if (father[node] != father[father[node]])
        father[node] = find(father[node]);
    return father[node];
}

bool unite(int a, int b) {
    a = find(a), b = find(b);

    if (a == b)
        return false;

    if (h[a] < h[b])
        father[a] = b;
    else {
        if (h[a] == h[b])
            ++ h[a];
        father[b] = a;
    }
    return true;
}

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

    cin >> N >> M;
    init();
    for (int i = 1; i <= M; ++ i)
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
    sort(edges + 1, edges + M + 1);

    vector <int> sol;

    int ans = 0;
    for (int i = 1; i <= M; ++ i)
        if (unite(edges[i].a, edges[i].b)) {
            ans += edges[i].c;
            sol.push_back(i);
        }

    cout << ans << '\n';
    cout << N - 1 << '\n';

    for (auto it: sol)
        cout << edges[it].a << ' ' << edges[it].b << '\n';
    return 0;
}