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

using namespace std;

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

const int nmax = 2 * 1e5 + 7;

vector<vector<pair<int, int>>> v;
bool viz[nmax], pus[nmax];
pair<int, int> ans[nmax];
set<pair<int, int>> s;
int mn[nmax], vc[nmax];

int main() {
    int n, m, q = 0, sum = 0;
    cin >> n >> m;
    v.resize(nmax);
    for(int i = 1; i <= m; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    s.insert({0, 1});
    viz[1] = 1;
    for(int i = 1; i <= n; i ++) {
        pair<int, int> p = *s.begin();
        s.erase(p);
        swap(p.first, p.second);
        pus[p.first] = 1;
        if(i >= 2) {
            ans[++ q] = {vc[p.first], p.first};
            sum += mn[p.first];
        }
        for(int j = 0; j < v[p.first].size(); j ++) {
            int vecin = v[p.first][j].first;
            int cost = v[p.first][j].second;
            if(pus[vecin]) {
                continue;
            }
            if(!viz[vecin] || cost < mn[vecin]) {
                if(!viz[vecin]) {
                    s.insert({cost, vecin});
                } else {
                    s.erase({mn[vecin], vecin});
                    s.insert({cost, vecin});
                }
                viz[vecin] = 1;
                mn[vecin] = cost;
                vc[vecin] = p.first;
            }
        }
    }
    cout << sum << '\n' << n - 1 << '\n';
    for(int i = 1; i <= q; i ++) {
        cout << ans[i].first << " " << ans[i].second << '\n';
    }
    return 0;
}