#include <bits/stdc++.h>
using namespace std;

string file = "apm";
ifstream fin(file + ".in");
ofstream fout(file + ".out");

struct poz {
    int i, j, c;
}M[400001];
int t[200001];
int rad(int x) {
    while (t[x] == x)
        return x;
    return t[x] = rad(t[x]);
}
bool cond(poz a, poz b) {
    if (a.c < b.c)
        return 1;
    return 0;
}
int main(){

    fin.tie(0);
    fout.tie(0);

    int n, m;
    fin >> n >> m;
    int i, j, k;
    for (i = 1; i <= n; i++)
        t[i] = i;
    m = 0;
    while (fin >> i >> j >> k)
    {
        m++;
        M[m].i = i;
        M[m].j = j;
        M[m].c = k;
    }
    sort(M + 1, M + m + 1, cond);
    int s = 0;
    vector<pair<int, int>> R;
    for (i = 1; i <= m; i++)
    {
        int r1 = rad(M[i].i);
        int r2 = rad(M[i].j);
        if (r1 != r2)
        {
            R.push_back(make_pair(M[i].i, M[i].j));
            s += M[i].c;
            t[r1] = r2;
        }
    }
    fout << s << '\n' << n - 1 << '\n';
    for (auto i : R)
        fout << i.first << ' ' << i.second << '\n';
    return 0;
}