#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int max_size = 2e5 + 1;

struct str{
    int from, to, cost;
    bool operator < (const str & aux) const
    {
        return cost > aux.cost;
    }
};

vector <pair <int, int>> mc[max_size];
pair <int, int> apm[max_size];
priority_queue <str> pq;
int uz[max_size];

int main ()
{
    int n, m;
    in >> n >> m;
    while (m--)
    {
        int x, y, c;
        in >> x >> y >> c;
        mc[x].push_back({y, c});
        mc[y].push_back({x, c});
    }
    uz[1] = 1;
    for (auto f : mc[1])
    {
        pq.push({1, f.first, f.second});
    }
    int ct = 1, ans = 0;
    while (ct < n)
    {
        str x = pq.top();
        pq.pop();
        if (!uz[x.to])
        {
            ans += x.cost;
            apm[ct] = {x.from, x.to};
            ct++;
            uz[x.to] = 1;
            for (auto f : mc[x.to])
            {
                if (!uz[f.first])
                {
                    pq.push({x.to, f.first, f.second});
                }
            }
        }
    }
    out << ans << '\n' << n - 1 << '\n';
    for (int i = 1; i < n; i++)
    {
        out << apm[i].first << " " << apm[i].second << '\n';
    }
    in.close();
    out.close();
    return 0;
}