#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct muchie
{
    int x, y, c;
}v[400001];

pair <int, int> p[400001];
int n, m, s, tata[400001], k, rg[400001];

inline bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

inline void citire()
{
    in >> n >> m;
    for (int i = 1; i <= m; ++i)
        in >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
}

inline int Find(int nod)
{
    while (tata[nod] != nod)
        nod = tata[nod];
    return nod;
}

inline void Unite(int x, int y)
{
    if (rg[x] < rg[y])
        tata[x] = y;
    if (rg[y] < rg[x])
        tata[y] = x;
    if (rg[y] == rg[x])
    {
        tata[x] = y;
        ++rg[y];
    }
}

inline void solve()
{
    for (int i = 1; i <= m; ++i)
    {
        if (Find(v[i].x) != Find(v[i].y))
        {
            Unite(Find(v[i].x), Find(v[i].y));
            p[++k].first = v[i].x;
            p[k].second = v[i].y;
            s += v[i].c;
        }
    }
}

int main()
{
    citire();
    for (int i = 1; i <= m; ++i)
    {
        tata[i] = i;
        rg[i] = 1;
    }
    solve();
    out << s << '\n' << n - 1 << '\n';
    for (int i = 1; i <= k; ++i)
        out << p[i].first << " " << p[i].second << '\n';
    return 0;
}