#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;
vector<bool> ok;
vector<int> t, rez;

struct muchie
{
    int a, b, cost, i;
} muchii[400003];

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

    t.resize(n + 1);
    for (int i = 1; i <= n; i++)
        t[i] = i;

    for (int i = 1, a, b, c; i <= m; i++)
        f >> a >> b >> c, muchii[i] = {a, b, c, i};

    sort(muchii + 1, muchii + m + 1, cmp);

    kruskal();

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

    return 0;
}