#include <bits/stdc++.h>
#define nmax 200005

using namespace std;

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

int tata[nmax], h[nmax];

struct muchie {
    int x, y, c;
};

vector <muchie> q;
vector <pair <int, int> > sol;

bool cmp (muchie a, muchie b) {
    return a.c < b.c;
}

void unire (int a, int b) {
    if (h[a] > h[b]) tata[b] = a;
    else tata[a] = b;
    if (h[a] == h[b]) h[b]++;
}

int gasire (int a) {
    int r = a;
    while (tata[r]) r = tata[r];
    int y = a, temp;
    while (y != r) {
        temp = tata[y];
        tata[y] = r;
        y = temp;
    }
    return r;
}

int main()
{
    int n, m, i;
    fin >> n >> m;
    muchie temp;
    for (int i = 1; i <= m; ++i) {
        fin >> temp.x >> temp.y >> temp.c;
        q.push_back(temp);
    }
    sort(q.begin(), q.end(), cmp);
    int sol1 = 0, x, y, c;
    for (i = 0; i < q.size(); ++i) {
        x = q[i].x;
        y = q[i].y;
        c = q[i].c;
        int root1 = gasire(x), root2 = gasire(y);
        if (root1 != root2) {
            sol1 += c;
            sol.push_back(make_pair(x, y));
            unire(root1, root2);
        }
    }
    fout << sol1 << "\n";
    fout << n - 1 << "\n";
    for (i = 0; i < n - 1; ++i) {
        fout << sol[i].first << " " << sol[i].second << "\n";
    }

    return 0;
}