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

using namespace std;

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

int n;
struct muchii
{
    int x, y, nr;
}v[400002], sol[400002];

struct DSU
{
    vector < int > parent, sizes;

    void init()
    {
        parent.resize(n + 1);
        sizes.resize(n + 1);
        for(int i = 1; i <= n; i++)
        {
            parent[i] = i;
            sizes[i] = 1;
        }
    }

    int find(int u)
    {
        if(u == parent[u])
            return u;
        parent[u] = find(parent[u]);
        return parent[u];
    }

    bool unite(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v)
            return false;
        if(sizes[v] > sizes[u])
            swap(u, v);
        parent[v] = u;
        sizes[u] += sizes[v];
        sizes[v] = 0;
        return true;
    }
}dsu;

bool cmp(muchii a, muchii b)
{
    if(a.nr != b.nr)
        return a.nr < b.nr;
    else if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

int main()
{
    int m, a, b, x, poz = 0, cost = 0;
    cin >> n >> m;
    dsu.init();
    for(int i = 1; i <= m; i++)
        cin >> v[i].x >> v[i].y >> v[i].nr;
    sort(v + 1, v + m + 1, cmp);

    for(int i = 1; i <= m; i++)
    {
        if(dsu.unite(v[i].x, v[i].y) == true)
        {
            cost += v[i].nr;
            sol[++poz] = v[i];
        }
    }
    cout << cost << '\n' << poz << '\n';
    for(int i = 1; i <= poz; i++)
        cout << sol[i].x << " " << sol[i].y << '\n';

    return 0;
}