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

using namespace std;

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

int n, m, sol = 0;
vector <int> x, y, c, a, s, v;

int f(int x)
{
    if (a[x] == x) return x;
    a[x] = f(a[x]);
    return a[x];
}

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

void read()
{
    cin >> n >> m;
    a.resize(n + 1);
    x.resize(m);
    y.resize(m);
    c.resize(m);
    s.resize(m);

    for (int i = 0; i < a.size(); i++) a[i] = i;

    for (int i = 0; i < x.size(); i++)
    {
        cin >> x[i] >> y[i] >> c[i];
        s[i] = i;
    }
}

void solve()
{
    sort(s.begin(), s.end(), comp);

    for (int i = 0; i < s.size(); i++)
        if (f(x[s[i] ]) != f(y[s[i] ]))
        {
            sol += c[s[i] ];
            a[f(x[s[i] ])] = f(y[s[i] ]);
            v.push_back(s[i]);
        }
}

void write()
{
    cout << sol << '\n' << v.size() << '\n';
    for (int i = 0; i < v.size(); i++)
        cout << x[v[i] ] << ' ' << y[v[i] ] << '\n';
}

int main()
{
    read();

    solve();

    write();

    return 0;
}