#include <fstream>
#include <vector>
#include <algorithm>

#define NMAX 200005
#define MMAX 400005
#define f first
#define s second
using namespace std;

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

int t[NMAX];
//vector <pair <int, int> > G[NMAX];
pair <int, pair < int, int> > M[MMAX];
vector <int> sol;

void init(int n)
{
    sol.reserve(n);
    for (int i = 1; i <= n; ++i)
        t[i] = i;
}
int grupa(int x)
{
    if (x == t[x]) return x;
    t[x] = grupa(t[x]);
    return t[x];
}
int main()
{
    int n, m;
    int x, y, c;
    int g1, g2;
    int cost = 0;

    fin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> c;
        M[i] = make_pair(c, make_pair(x, y));
    }
    sort(M, M + m);

    init(n);
    for (int i = 0; (i < m) && (sol.size() < n - 1); ++i)
    {
        g1 = grupa(M[i].s.f);
        g2 = grupa(M[i].s.s);
        if (g1 != g2)
        {
            t[g1] = g2;
            sol.push_back(i);
            cost += M[i].f;
        }

    }

    fout << cost << '\n' << n - 1 << '\n';
    for (int i = 0; i < (n - 1); ++i)
        fout << M[sol[i]].s.f << ' ' << M[sol[i]].s.s << '\n';

    return 0;
}