#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

const int NMAX = 2e5 + 5;
int h[NMAX], father[NMAX];
int sol;
int n, m;

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

struct edge {
    int x, y, c;
    inline bool operator< (const edge &b) const {
        return c < b.c;
    }
};

vector <edge> v;
vector <pair <int, int> > q;

void unite(int root1, int root2) {
    if (h[root1] > h[root2]) father[root2] = root1;
    else father[root1] = root2;
    if (h[root1] == h[root2]) h[root2]++;
}

int find_root(int x) {
    int r = x;
    while (father[r]) r = father[r];
    int y = x, t;
    while (y != r) {
        t = father[y];
        father[y] = r;
        y = t;
    }
    return r;
}

void preprocess() {
    fin >> n >> m;
    edge temp;
    for (int i = 1; i <= m; ++i) {
        fin >> temp.x >> temp.y >> temp.c;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
}

void solve() {
    int sol = 0, x, i, y, c;
    int root1, root2;
    for (i = 0; i < m; ++i) {
        x = v[i].x;
        y = v[i].y;
        c = v[i].c;
        root1 = find_root(x);
        root2 = find_root(y);
        if (root1 != root2) {
            sol += c;
            q.push_back(make_pair(x, y));
            unite(root1, root2);
        }
    }
    fout << sol << "\n" << n - 1 << "\n";
    for (i = 0; i < n - 1; ++i)
        fout << q[i].first << " " << q[i].second << '\n';
}
int main()
{
    preprocess();
    solve();
    return 0;
}