#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int MMAX = 400000;
const int NMAX = 200000;

int n, m;
int u, v, w;
int parent[NMAX + 1];
struct muchie{
    int u, v, w;
};
muchie e[MMAX + 1], sol[NMAX + 1];

int Find (int x) {
    if (x == parent[x])
        return x;
    return parent[x] = Find(parent[x]);
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e + 1, e + m + 1, [](muchie a, muchie b) {
         return a.w < b.w;
         });
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    int nr = 0;
    for (int i = 1; i <= m; i++) {
        int x = Find(e[i].u);
        int y = Find(e[i].v);
        if (x != y) {
            parent[x] = y;
            sol[nr++] = e[i];
        }
    }
    int cost = 0;
    for (int i = 0; i < n - 1; i++) {
        cost += sol[i].w;
    }
    fout << cost << '\n' << n - 1 << '\n';
    for (int i = 0; i < n - 1; i++) {
        fout << sol[i].u << ' ' << sol[i].v << '\n';
    }
    return 0;
}