#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x, y, c;
}v[400005], memorare[400005];

int n, m, r[200005], k, i, cnt, nr1, nr2, t[200005],tx, ty;
long long cst;

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

int rad(int nod)
{
    while(t[nod] != nod)
        nod = t[nod];
    return nod;
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i++)
        f >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; i++)
        t[i] = i, r[i] = 1;
    for(int i = 1; i <= m; i++)
    {
        tx = rad(v[i].x);
        ty = rad(v[i].y);
        if(tx != ty)
        {
            cst += v[i].c;
            k++;
            memorare[k].x = v[i].x;
            memorare[k].y = v[i].y;
            if(r[tx] > r[ty])
                t[ty] = tx;
            else
            {
                t[tx] = ty;
                if(r[tx] == r[ty])
                    r[tx]++;
            }
         }
    }
    g << cst << endl << k << endl;
    for(i = 1; i <= k; i++)
        g << memorare[i].x << " " << memorare[i].y << endl;

    return 0;
}