#include <fstream>
#define N  200002
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int tata[N], rang[N];
struct bla
{
    int a, b, c;
}arb[N];
struct bla1
{
    int x, y;
}sol[N];
bool cmp(bla A, bla B)
{
    return (A.c < B.c);
}
int root(int nod)
{
    while (nod != tata[nod])
        nod = tata[nod];
    return nod;
}
void unite(int ra, int rb)
{
    if (rang[ra] < rang[rb])
        tata[ra] = tata[rb];
    else
        tata[rb] = tata[ra];
    if (rang[ra] == rang[rb])
        ++rang[ra];
}
int main()
{
    int n, m, ss = 0, nr = 0, ra, rb;
    f >> n >> m;
    for (int i = 1;i <= m;++i)
        f >> arb[i].a >> arb[i].b >> arb[i].c;
    for (int i = 1;i <= n;++i) tata[i] = i;
    sort(arb + 1, arb + m + 1, cmp);
    for (int i = 1;i <= m;++i)
    {
        ra = root(arb[i].a);
        rb = root(arb[i].b);
        if (ra != rb)
        {
            ss += arb[i].c;
            ++nr;
            sol[nr] = { arb[i].a,arb[i].b };
            unite(ra, rb);
        }
    }
    g << ss << '\n' << nr << '\n';
    for (int i = 1;i <= nr;++i)
        g << sol[i].x << ' ' << sol[i].y << '\n';
    f.close();
    g.close();
    return 0;
}