#include <bits/stdc++.h>
using namespace std;
string np = "apm";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n, m, ctotal, t[400003], ind[400003];
struct muchie
{
    int a, b, cost;
} muchii[400003];
vector<int> rez;

bool cmp(int i, int j)
{
    return muchii[i].cost < muchii[j].cost;
}
int find_set(int nod)
{
    if (t[nod] == nod)
        return nod;
    return t[nod] = find_set(t[nod]);
}
void union_set(int a, int b)
{
    t[find_set(a)] = find_set(b);
}
void kruskal()
{
    for (int i = 1; i <= n; i++)
        t[i] = i;
    sort(ind + 1, ind + m + 1, cmp);
    for (int i = 1; i <= m; i++)
        if (find_set(muchii[ind[i]].a) != find_set(muchii[ind[i]].b))
            ctotal += muchii[ind[i]].cost, rez.push_back(ind[i]),
                union_set(muchii[ind[i]].a, muchii[ind[i]].b);
}
int main()
{
    f >> n >> m;
    for (int i = 1, a, b, cost; i <= m; i++)
        f >> a >> b >> cost, ind[i] = i, muchii[i] = {a, b, cost};

    kruskal();

    g << ctotal << '\n';
    g << n - 1 << '\n';
    for (auto i : rez)
        g << muchii[i].a << " " << muchii[i].b << '\n';

    return 0;
}