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

using namespace std;

struct Edge
{
    int u, v, w;
    bool operator < (Edge const& other)
    {
        return w < other.w;
    }
};

const int Nmax = 200000;
vector <Edge> edges;
int tree_id[Nmax + 1];
vector <Edge> ans;

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    for (int i = 1; i <= n; i++)
    {
        tree_id[i] = i;
    }
    sort(edges.begin(), edges.end());
    int cost = 0;
    for (Edge e : edges)
    {
        if (tree_id[e.u] != tree_id[e.v])
        {
            cost += e.w;
            ans.push_back(e);
            int old = tree_id[e.u], new_id = tree_id[e.v];
            for (int i = 1; i <= n; i++)
            {
                if (tree_id[i] == old)
                {
                    tree_id[i] = new_id;
                }
            }
        }
    }
    fout << cost << "\n";
    fout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); i++)
    {
        fout << ans[i].u << " " << ans[i].v << "\n";
    }
    return 0;
}