#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

int n, m, dist[200001], viz[200001], tata[200001], sum;
vector<pair<int, int>> gf[200001];
set<pair<int, int>> s;
const int INF = 2e9;

void prim(int start) {
    dist[start] = 0;
    viz[start] = 1;
    s.insert({ dist[start], start });
    while (!s.empty()) {
        int cost = s.begin()->first;
        int nod = s.begin()->second;
        s.erase(s.begin());
        viz[nod] = 1;
        sum += cost;
        for (auto vecin : gf[nod]) {
            int costnou = vecin.first;
            int nodnou = vecin.second;
            if (!viz[nodnou] && dist[nodnou] > costnou) {
                s.erase({ dist[nodnou], nodnou });
                dist[nodnou] = costnou;
                s.insert({ dist[nodnou], nodnou });
                tata[nodnou] = nod;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        gf[x].push_back({ c, y });
        gf[y].push_back({ c, x });
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    prim(1);
    fout << sum << "\n" << n - 1 << "\n";
    for (int i = 2; i <= n; i++)
        fout << tata[i] << " " << i << "\n";
    return 0;
}