#include <fstream>
#include <algorithm>
#define NMAX 200010

using namespace std;

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

struct edge
{
    int e1, e2, cost;
};

edge p[400010];
int n, m, SE, c[NMAX], A[NMAX], cost, nn;
bool marked[NMAX];

int criteriu(edge A, edge B)
{
    if(A.cost > B.cost) return 0;
    return 1;
}

int main()
{
    int i, j, mini, maxi;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
        fin >> p[i].e1 >> p[i].e2 >> p[i].cost;
    sort(p + 1, p + m + 1, criteriu);
    for(i = 1; i <= n; i++)
        c[i] = i;
    for(i = 1; SE < n - 1; i++)
        if(c[p[i].e1] != c[p[i].e2])
        {
            A[++SE] = i;
            cost += p[i].cost;
            marked[i] = 1;
            ++nn;
            if(c[p[i].e1] < c[p[i].e2])
            {
                mini = c[p[i].e1];
                maxi = c[p[i].e2];
            }
            else
            {
                mini = c[p[i].e2];
                maxi = c[p[i].e1];
            }
            for(j = 1; j <= n; j++)
                if(c[j] == maxi)
                c[j] = mini;
        }
    fout << cost << '\n';
    fout << nn << '\n';
    for(i = 1; i <= m; i++)
        if(marked[i] != 0)
        fout << p[i].e1 << ' '<< p[i].e2<< '\n';
    return 0;
}