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

using namespace std;

using Edge = tuple<int, int, int>;
using Graph = vector<Edge>;
using SimpleGraph = vector<pair<int, int>>;

int FindFather(vector<int> &fa, int x)
{
    if (fa[x] == -1) {
        return x;
    }
    return (fa[x] = FindFather(fa, fa[x]));
}

inline bool Connected(vector<int> &fa, int x, int y)
{
    return FindFather(fa, x) == FindFather(fa, y);
}

inline void Unite(vector<int> &fa, int x, int y)
{
    int fx = FindFather(fa, x);
    int fy = FindFather(fa, y);
    if (fx != fy) {
        fa[fy] = fx;
    }
}

pair<int, SimpleGraph> FindApm(Graph &g, int n)
{
    vector<int> fathers(n, -1);
    SimpleGraph edges(n - 1);

    int min_cost = 0;
    int edges_index = 0;

    sort(g.begin(), g.end());
    for (const auto &edge : g) {
        int x = get<1>(edge);
        int y = get<2>(edge);

        if (!Connected(fathers, x, y)) {
            Unite(fathers, x, y);
            min_cost += get<0>(edge);

            edges[edges_index++] = {x, y};
            if (edges_index == n) {
                break;
            }
        }
    }
    return {min_cost, edges};
}

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

    int n, m;
    fin >> n >> m;

    Graph graph(m);
    for (auto &edge : graph) {
        int x, y, c;
        fin >> x >> y >> c;
        edge = make_tuple(c, x - 1, y - 1);
    }

    auto apm = FindApm(graph, n);
    fout << apm.first << "\n" << n - 1 << "\n";
    for (const auto &edge : apm.second) {
        fout << edge.first + 1 << " " << edge.second + 1 << "\n";
    }

    return 0;
}