#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define inf 0x3f3f3f3f
using namespace std;

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

vector<vector<pair<int, int>>> v(200001);

vector<pair<int, int>> prim(int s, int n, int m, int &c) {
    vector<int> d(n + 1, inf), t(n + 1, 0);
    vector<bool> sel(n + 1, false);
    vector<pair<int, int>> sol;
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
    Q.push({0, s});
    int nr = 0;
    int next, cost;
    while (nr < n) {
        auto nod = Q.top();
        Q.pop();
        if (sel[nod.second])
            continue;
        nr++;
        sol.push_back({t[nod.second], nod.second});
        c += d[nod.second];
        sel[nod.second] = true;
        for(auto&& vecin : v[nod.second]) {
            cost = vecin.first;
            next = vecin.second;
            if (d[next] > cost && !sel[next]) {
                d[next] = cost;
                t[next] = nod.second;
                Q.push({d[next], next});
            }
        }
    }
    sol.erase(sol.begin());
    return sol;
}

int main() {
    int n, m;
    int a, b, c, cost = 0;
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> a >> b >> c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});   
    }
    vector<pair<int, int>> sol = prim(1, n, m, cost);
    out << cost << "\n" << n - 1 << "\n";
    for (auto i: sol) {
        out << i.first << " " << i.second << "\n";
    }
    return 0;
}