#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

struct edge{
    int left, right, cost;

    bool operator<(const edge& other) const {
        return cost > other.cost;
    }
};

int n, m, total;
int father[200100], depth[200100];
queue<pair<int, int>> ans;
priority_queue<edge> q;

int root(int node)
{
    int x = node;

    while(father[x] != 0)
        x = father[x];

    int y = node;

    while(father[y] != 0)
    {
        int aux = y;
        y = father[y];
        father[aux] = x;
    }

    return x;
}

int connect(int x, int y)
{
    if(depth[x] > depth[y])
        father[y] = x;

    if(depth[x] < depth[y])
        father[x] = y;

    if(depth[x] == depth[y])
    {
        father[x] = y;
        depth[y]++;
    }
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;

        q.push({x, y, cost});
    }

    while(!q.empty())
    {
        edge x = q.top();
        q.pop();

        int rootLeft = root(x.left);
        int rootRight = root(x.right);

        if(rootLeft != rootRight)
        {
            connect(rootLeft, rootRight);

            total += x.cost;
            ans.emplace(x.left, x.right);
        }
    }

    out << total << '\n' << ans.size() << '\n';

    while(!ans.empty())
    {
        out << ans.front().first << ' ' << ans.front().second << '\n';
        ans.pop();
    }

    return 0;
}