#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, cost, t[200003], d[200003];
struct muchie
{
    int a, b, c, i;
};
vector<bool> ok;
vector<muchie> muchii;

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}
int find_set(int nod)
{
    if (nod == t[nod])
        return nod;
    return t[nod] = find_set(t[nod]);
}
void union_sets(int a, int b)
{
    a = find_set(a);
    b = find_set(b);
    if (a != b)
    {
        if (d[a] < d[b])
            swap(a, b);
        t[b] = a;
        d[a] += d[b];
    }
}
void kruskal()
{
    sort(muchii.begin(), muchii.end(), cmp);
    ok.resize(m + 1);
    for (int i = 1; i <= n; i++)
        t[i] = i, d[i] = 1;

    for (auto u : muchii)
        if (find_set(u.a) != find_set(u.b))
            cost += u.c, ok[u.i] = 1, union_sets(u.a, u.b);
}
int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);

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

    kruskal();

    g << cost << '\n';
    g << n - 1 << '\n';
    for (auto muchie : muchii)
        if (ok[muchie.i])
            g << muchie.a << " " << muchie.b << '\n';

    return 0;
}