#include <bits/stdc++.h>

#define llg     long long

#define MAXN    200005
#define FILE    std::string("apm")

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

std::ifstream input (FILE+".in");
std::ofstream output(FILE+".out");

int N, M;
std::vector <Edge> edges;
inline void addEdge(int x, int y, int w) {
    edges.push_back({x, y, w});
}   int rang[MAXN], parent[MAXN];

int _find(int x) {
    if (parent[x] != x) return parent[x] = _find(parent[x]);
    return x;
}
void _union(int x, int y) {
    if (x == y) return;
    if (rang[x] > rang[y]) parent[y] = x;
    else                   parent[x] = y;
    if (rang[x] == rang[y]) ++ rang[y];
}
void _query(int x, int y) {
    output << (_find(x) == _find(y) ? "DA\n" : "NU\n");
}

int main()
{
    input >> N >> M;
    for (int i=0, x, y, w; i<M; ++i)
        input >> x >> y >> w, addEdge(x, y, w);
    for (int i=1; i<=N; ++i) parent[i] = i;
    std::sort(edges.begin(), edges.end());

    std::vector <std::pair <int, int>> sol;
    int sum = 0;
    for (int i=0, unionCnt=0; i<edges.size() && unionCnt < N-1; ++i) {
        int x = edges[i].x, y = edges[i].y;
        int fx = _find(x), fy = _find(y);
        if (fx == fy) continue;
        ++ unionCnt;
        _union(x, y);
        sum += edges[i].w;
        sol.push_back({x, y});
    }

    output << sum << '\n' << sol.size() << '\n';
    for (auto &it:sol) output << it.first << ' ' << it.second << '\n';

    return 0;
}