#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n  , m , t[400005] , rang[400005] , s , cnt;

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

mch muchie[400005] , aux[400005];

int radacina (int a)
{
    if (t[a] == 0)
        return a;
    else
    {
        int k = radacina (t[a]);
        t[a] = k;
        return k;
    }
}

void unire (int a , int b)
{
    int rx = radacina (a) , ry = radacina (b);
    if (rx != ry)
    {
        if (rang[rx] < rang[ry])
            t[rx] = ry;
        else
            if (rang[ry] < rang[rx])
            t[ry] = rx;
        else
            t[rx] = ry , rang[rx]++;
    }
}

bool cmp (mch a , mch b)
{
    if (a.c < b.c)
        return true;
    if (a.c == b.c && a.x < b.x)
        return true;
    return false;
}

int main()
{
    f >> n >> m;
    for (int i = 1 ; i <= m ; i++)
        f >> muchie[i].x >> muchie[i].y >> muchie[i].c;
        sort (muchie + 1 , muchie + m + 1 , cmp);

    for (int i = 1 ; i <= m ; i++)
    {
        int a = muchie[i].x , b = muchie[i].y , cost = muchie[i].c;
        if (radacina (a) != radacina (b))
        {
            s = s + cost;
            cnt++;
            aux[cnt] = muchie[i];
            unire (a , b);
        }
    }
    g << s << '\n' << cnt << '\n';;
    for (int i = 1 ; i <= cnt ; i++)
        g << aux[i].x <<" " << aux[i].y <<'\n';
    return 0;
}