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

using namespace std;

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

const int N = 2e5;
int tata[N + 1], rang[N + 1];

vector <pair <int, int> > sol;

struct ceva
{
    int x, y, cost;
    bool operator < (const ceva &a)const
    {
        return cost < a.cost;
    }
} a[N + 1];

int n, m, ans;

struct apm
{
    int rad (int x)///path compression
    {
        if (x == tata[x]) return x;
        return tata[x] = rad (tata[x]);
    }
    void unite (ceva x)
    {
        int rx = rad (x.x);
        int ry = rad (x.y);
        if (rx != ry)
        {
            if (rang[rx] == rang[ry])
                ++rang[ry];
            if (rang[rx] < rang[ry])
                tata[rx] = ry;
            else{
                tata[ry] = rx;
            }

            sol.push_back({x.x, x.y});
            ans += x.cost;
        }
    }

}v;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i].x >> a[i].y >> a[i].cost;
    sort (a + 1, a + m + 1);
    for (int i = 1; i <= n; ++i)
        tata[i] = i;
    for (int i = 1; i <= m; ++i)
        v.unite (a[i]);
    cout << ans << '\n' << sol.size() << '\n';
    for (auto it : sol)
        cout << it.first << ' ' << it.second << '\n';
    return 0;
}