#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define NMAX 200005

using namespace std;

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

int i, n, m, x, y, cost, s = 0, used = 1;
vector < pair < int, int > > sol, v[NMAX];
bool visited[NMAX];

struct apm
{
    int x, y, cost;
};

struct compare
{
    bool operator () (apm &a, apm &b)
    {
        return a.cost > b.cost;
    }
};

priority_queue < apm, vector < apm >, compare > pq;

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

    for (i = 1; i <= m; ++ i)
    {
        f >> x >> y >> cost;
        v[x].push_back(make_pair(y, cost));
        v[y].push_back(make_pair(x, cost));
    }

    visited[1] = 1;

    while (used <= n - 1)
    {
        for (i = 1; i <= n; ++ i)
            if (visited[i])
                for (auto &it : v[i])
                    if (!visited[it.first])
        {
            apm current;
            current.x = i;
            current.y = it.first;
            current.cost = it.second;
            pq.push(current);
        }

        apm current = pq.top();

        s += current.cost;
        visited[current.y] = 1;
        used ++;
        while (pq.size())
            pq.pop();
        sol.push_back(make_pair(current.x, current.y));
    }

    g << s << '\n' << sol.size() << '\n';

    for (auto &it : sol)
        g << it.first << " " << it.second << '\n';
    return 0;
}