#include <fstream>
#define mF "apm"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
constexpr int N = 200001; int A[N], T[N]; int R(int e) {if (0 < A[e]) return A[e] = R(A[e]); return e;}
#include <utility>
#define x first
#define y second
using P = std::pair<int, int>;
#include <vector>
std::vector<P> L[N];
#include <bitset>
std::bitset<N> E;
#include <queue>
int main()
{
    int n, m, s = 0; in >> n >> m; while (m--) {int a, b, c; in >> a >> b >> c; L[a].push_back({c, b}); L[b].push_back({c, a});}
    std::fill(A, A + n + 1, -1); std::priority_queue<std::pair<int, P>> Q; for (Q.push({0, {0, 1}}); Q.size();)
    {int t = Q.top().y.x, f = Q.top().y.y, c = -Q.top().x, a = R(t), b = R(f); Q.pop(); if (E[f] or a == b) continue;
    else T[f] = t, E[f] = true, s += c, [&a, &b](){if (A[a] < A[b]) std::swap(a, b); A[b] += A[a]; A[a] = b;}();
    for (auto p: L[f]) if (not E[p.y]) Q.push({-p.x, {f, p.y}});}
    out << s << '\n' << n-1 << '\n'; for (int f = 2; f <= n; f++) out << T[f] << ' ' << f << '\n';
}