#include <fstream>
#include <algorithm>
#include <vector>

#define MAXN 400005

using namespace std;

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

int n, m, ind[MAXN];
int gr[MAXN], a[MAXN], b[MAXN], c[MAXN];
int ans;
vector <int> vans;

int group(int x)
{
    if (gr[x] == x) return x;
    gr[x] = group(gr[x]);
    return gr[x];
}

void reunion(int x, int y)
{
    gr[group(x)] = group(y);
}

bool cmp(int x, int y)
{
    return c[x] < c[y];
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> a[i] >> b[i] >> c[i];
        ind[i] = i;
    }

    for (int i = 1; i <= n; ++i)
        gr[i] = i;

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

    for (int i = 1; i <= m; i++)
    {
        if (group(a[ind[i]]) != group(b[ind[i]]))
        {
            ans += c[ind[i]];
            reunion(a[ind[i]], b[ind[i]]);
            vans.push_back(ind[i]);
        }
    }

    fout << ans << '\n';
    fout << n - 1 << '\n';
    for (int i = 0; i < n - 1; ++i)
        fout << a[vans[i]] << ' ' << b[vans[i]] << '\n';

    return 0;
}