#include <fstream>
#include <algorithm>

using namespace std;

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

const int M = 400001;
const int N = 200001;

struct muchie{
    int x, y, c;
    bool ok;} q[M];

int n, m, k, s[N], sol, f;

bool comp(muchie a, muchie b){ return a.c < b.c; };

void citire()
{
    in >> n >> m;
    for(int i=1;i<=m;i++)
        in >> q[i].x >> q[i].y >> q[i].c;
}

void init()
{
    sort(q+1, q+m+1, comp);
    for(int i=1;i<=n;i++)
        s[i] = i;
}

int tata(int x)
{
    while(s[x] != x)
        x = s[x];

    return x;
}

void kruskal()
{
    while(f != n-1)
    {
        ++k;
        int X = tata(q[k].x);
        int Y = tata(q[k].y);
        if(X != Y)
        {
            if( X < Y)
                s[Y] = X;
            else
                s[X] = Y;

            sol += q[k].c;
            q[k].ok = true;
            f++;
        }
    }
}

void afisare()
{
    out << sol << "\n" << f << "\n";
    for(int i=1;i<=m;i++)
        if(q[i].ok)
            out << q[i].x << " " << q[i].y << "\n";
}

int main()
{
    citire();
    init();

    kruskal();
    afisare();


    in.close();
    out.close();
    return 0;
}