#include <fstream>
#include <algorithm>
using namespace std;
// Algoritmul lui Kruskal
ifstream in("apm.in");
ofstream out("apm.out");

const int maxn = 200001;
const int maxm = 400001;
int H[maxn];  // vectorul de tati
bool viz[maxm];

struct edge {
    int u, v, c;
} E[maxm];    // multimea muchiilor

bool comp(const edge &a, const edge &b) { return a.c < b.c; }

int father(int x)
{
    if (x != H[x])
        H[x] = father(H[x]);
    return H[x];
}

int main()
{
    int N, M, k = 1, ct = 0, v;
    in >> N >> M;

    for (int i = 1; i <= N; i++) H[i] = i;

    for (int i = 1; i <= M; i++)
        in >> E[i].u >> E[i].v >> E[i].c;

    sort(E+1, E+M+1, comp);

    for (int i = 1; i < N; i++)
    {
        while (father(E[k].u) == father(E[k].v)) ++k;

        H[father(E[k].v)] = father(E[k].u);
        viz[k] = true;
        ct += E[k].c;
        ++k;
    }
    out << ct << '\n' << N-1 << '\n';
    for (int i = 1; i <= M; i++)
        if (viz[i]) out << E[i].u << ' ' << E[i].v << '\n';

    return 0;
}