#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie 
{
    int x, y, c;
};
Muchie v[100005], sol[100005];
int cc[100005];
bool cmp(Muchie a, Muchie b) 
{
    return a.c < b.c;
}
int main() 
{
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
    for (int i = 1; i <= n; i++)
        cc[i] = i;
    int s = 0, nr = 0;
    for (int i = 1; i <= m; i++) 
    {
        int x = v[i].x;
        int y = v[i].y;
        if (cc[x] != cc[y]) 
        {
            s += v[i].c;
            nr++;

            sol[nr] = v[i];

            int veche = cc[y];
            int noua = cc[x];

            for (int j = 1; j <= n; j++)
                if (cc[j] == veche)
                    cc[j] = noua;
            if (nr == n - 1)
                break;
        }
    }
    fout << s << '\n';
    fout << nr << '\n';
    for (int i = 1; i <= nr; i++)
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    return 0;
}