#include <fstream>
#include <algorithm>

#define x first
#define y second
#define NMAX 400010

using namespace std;

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

int unu(int nod);

pair<int, pair<int, int> > V[NMAX], aux;
pair<int, int> M[NMAX/2];
int n, m, i, a, b, c, tata[NMAX/2], nrmuchii, cost;

int main()
{
    fin >> n >> m;
    for(i = 1; i <= n; ++i)
        tata[i] = -1;
    for(i = 1; i <= m; ++i)
    {
        fin >> a >> b >> c;
        aux.x = c;
        aux.y.x = a;
        aux.y.y = b;
        V[i] = aux;
    }
    sort(V+1, V+m+1);
    for(i = 1; i <= m && nrmuchii < n-1; ++i)
    {
        a = unu(V[i].y.x);
        b = unu(V[i].y.y);
        if(a != b)
        {
            tata[a] = b;
            nrmuchii++;
            M[nrmuchii].x = a;
            M[nrmuchii].y = b;
            cost += V[i].x;
        }
    }
    fout << cost << '\n';
    fout << nrmuchii << '\n';
    for(i = 1; i <= nrmuchii; ++i)
        fout << M[i].x << ' ' << M[i].y << '\n';
    return 0;
}

int unu(int nod)
{
    if(tata[nod] == -1)
        return nod;
    else
    {
        tata[nod] = unu(tata[nod]);
        return tata[nod];
    }
}