#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N = 200005;
const int M = 400005;

struct muchie
{
    int x, y, cost;
};
muchie m[M], arb[N];

int tata[N], niv[N];

bool cmp(muchie a, muchie b)
{
    return (a.cost < b.cost);
}

void myunion(int rad1, int rad2)
{
    if(niv[rad1] < niv[rad2])
        tata[rad1] = rad2;
    else if(niv[rad1] > niv[rad2])
        tata[rad2] = rad1;
    else
    {
        tata[rad2] = rad1;
        niv[rad1] ++;
    }
}
int find(int x)
{
    int rad = x, y;
    while(tata[rad] != rad)
        rad = tata[rad];
    while(tata[x] != rad)
        {
            y = tata[x];
            tata[x] = rad;
            x = y;
        }
    return rad;

}

int main()
{
    int n, muchii;
    in >> n >> muchii;
    int i;
    for(i = 1; i <= muchii; i++)
    {
        in >> m[i].x >> m[i].y >> m[i].cost;
    }
    for(i = 1; i <= n; i++)
        tata[i] = i;
    sort(&m[1], &m[muchii + 1], cmp);
    int a, b, r1, r2;
    int cnt = 0;
    int costminim = 0;
    for(i = 1; i <= muchii; i++)
    {
        a = m[i].x;
        b = m[i].y;
        r1 = find(a);
        r2 = find(b);
        if(r1 != r2)
        {
            cnt++;
            arb[cnt] = m[i];
            costminim += m[i].cost;
            myunion(r1, r2);
        }
    }
    out << costminim <<"\n"<<cnt<<"\n";
    for(i = 1; i <= cnt; i++)
        out << arb[i].x <<" "<< arb[i].y<<"\n";
    return 0;
}