#include <bits/stdc++.h>

using namespace std;

typedef pair<int, pair<int, int>> ppi;

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

vector<ppi> edges;
vector<int> level;
vector<int> father;
vector<int> chosen;

class Comparator
{
public:
    bool operator()(const ppi &a, const ppi &b)
    {
        return a.second.second < b.second.second;
    }
};

int getFather(int x)
{
    if (father[x] == x)
        return x;

    int tata = getFather(father[x]);
    father[x] = tata;
    return tata;
}

int _union(int x, int y)
{
    if (level[x] >= level[y])
        father[y] = x;
    else
        father[x] = y;

    if (level[x] == level[y])
        ++level[x];
}

int main()
{
    int n, m;

    fin >> n >> m;

    level.resize(n + 1);
    father.resize(n + 1);
    chosen.resize(m + 1, 0);

    for (int i = 1; i <= n; ++i)
    {
        level[i] = 1;
        father[i] = i;
    }

    for (int x, y, c, i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        edges.push_back(make_pair(x, make_pair(y, c)));
    }

    sort(edges.begin(), edges.end(), Comparator());

    int i = 0;
    int sum = 0;
    for (const ppi& p: edges)
    {
        int x = p.first;
        int y = p.second.first;
        int c = p.second.second;

        if ((x = getFather(x)) != (y = getFather(y)))
        {
            _union(x, y);
            chosen[i] = 1;
            sum += c;
        }
        i++;
    }

    fout << sum << '\n' << n - 1 << '\n';

    for (int i = 0; i < edges.size(); ++i)
        if (chosen[i])
            fout << edges[i].first << " " << edges[i].second.first << "\n";

    return 0;
}