#include <fstream>
#include <algorithm>

using namespace std;

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

struct trio
{
    int x, y, c;
};

const int N = 400001;
int n, m;
trio g[N];
int t[N], nr[N];
bool folosit[N];

bool cmp(trio st, trio dr)
{
    return st.c < dr.c;
}

int radacina(int x)
{
    if(t[x] == 0)
    {
        return x;
    }
    t[x] = radacina(t[x]);
    return t[x];
}

void reuniune(int x, int y)
{
    int rx = radacina(x), ry = radacina(y);
    if(rx == ry)
    {
        return;
    }
    if(nr[rx] < nr[ry])
    {
        t[rx] = ry;
        nr[ry] += nr[rx];
    }
    else
    {
        t[ry] = rx;
        nr[rx] += nr[ry];
    }
}

bool interogare(int x, int y)
{
    return (radacina(x) == radacina(y));
}


int main()
{
    in >> n >> m;
    int cost = 0, nrm = 0;
    for(int i = 0; i < m; i++)
    {
        in >> g[i].x >> g[i].y >> g[i].c;
    }
    sort(g, g + m, cmp);
    for(int i = 1; i <= n; i++)
    {
        nr[i] = 1;
    }
    for(int i = 0; i < m; i++)
    {
        int x = g[i].x, y = g[i].y, c = g[i].c;
        if(!interogare(x, y))
        {
            folosit[i] = true;
            cost += c;
            reuniune(x,y);
            nrm++;
        }
    }
    out << cost << '\n';
    out << nrm << '\n';
    for(int i = 0; i < m; i++)
    {
        if(folosit[i])
        {
            out << g[i].x << ' ' << g[i].y << '\n';
        }
    }
    return 0;
}