#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int tata[200005], niv[200005];

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

muchie m[400005], arb[200005];
int N, M;

bool cmp (muchie a, muchie b)
{
    if(a.c < b.c) return true;
    else return false;
}

void myunion(int r1, int r2)
{
    if(niv[r1] < niv[r2])
        tata[r1] = r2;
    else if(niv[r1] > niv[r2])
        tata[r2] = r1;
    else
    {
        tata[r1] = r2;
        niv[r2]++;
    }
}

int find(int x)
{
    int y, rad = x;
    while(tata[rad] != rad)
        rad = tata[rad];
    while(tata[x] != x)
    {
        y = tata[x];
        tata[x] = rad;
        x = y;
    }
    return rad;
}

int main()
{
    in >> N >> M;
    int i;
    for(i = 1; i <= M; i++)
        in >> m[i].x >> m[i].y >> m[i].c;

    sort(&m[1], &m[M+1], cmp);

    for(i = 1; i <= N; i++)
        tata[i] = i;

    int a, b, rad1, rad2;
    int cnt = 1, suma = 0;

    for(i = 1; i <= M; i++)
    {
        a = m[i].x;
        b = m[i].y;
        rad1 = find(a);
        rad2 = find(b);
        if(rad1 != rad2)
        {
            arb[cnt] = m[i];
            cnt++;
            suma += m[i].c;
            myunion(rad1, rad2);

        }

    }
    out <<suma<<"\n"<<N-1 <<"\n";
    for(i = 1; i < cnt; i++)
    {
        out<<arb[i].x <<" "<< arb[i].y <<"\n";
    }

    return 0;
}